Submission #1674652
Source Code Expand
#include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <set> #include <iostream> #include <string> #include <vector> #include <algorithm> #include <sstream> #include <complex> #include <stack> #include <queue> #include <cstdio> #include <cstring> #include <iterator> #include <bitset> #include <unordered_set> #include <unordered_map> #include <fstream> #include <iomanip> #include <cassert> #include <utility> #include <memory> #include <functional> #include <deque> #include <cctype> #include <ctime> #include <numeric> #include <list> #include <iomanip> #if __cplusplus >= 201103L #include <array> #include <tuple> #include <initializer_list> #include <forward_list> #define cauto const auto& #else #endif using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vint; typedef vector<vector<int> > vvint; typedef vector<long long> vll; typedef vector<vector<long long> > vvll; #define VV(T) vector<vector< T > > template <class T> void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){ v.assign(a, vector<T>(b, t)); } template <class F, class T> void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #define GET_MACRO(_1, _2, _3, NAME, ...) NAME #define _rep(i,n) _rep2((i),0,(n)) #define _rep2(i,a,b) for(int i=(a);i<(b);++i) #define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define fi first #define se second #define mkp make_pair #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define MOD 1000000007LL #define EPS 1e-8 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define maxs(x,y) x=max(x,y) #define mins(x,y) x=min(x,y) int dp[4010][2010]; template<class T> struct RollingHash { static const int NN = 2; // the number of hash table T base[NN] = {1009, 1007}; T PMOD[NN] = {1000000007, 1000000009}; vector<T> hash[NN]; vector<T> mypow[NN]; int sz; void init(string s) { sz = s.size(); for(int i = 0; i < NN; i++) { hash[i].assign(sz + 1, 0); mypow[i].assign(sz + 1, 0); mypow[i][0] = 1; } for(int i = 0; i < NN; i++) { for(int j = 0; j < sz; j++) { hash[i][j + 1] = (hash[i][j] * base[i] + s[j]) % PMOD[i]; mypow[i][j + 1] = mypow[i][j] * base[i] % PMOD[i]; } } } RollingHash() { } // hash[t] value of s[l..r] T get(int l, int r, int t) { T ret = (hash[t][r + 1] - hash[t][l] * mypow[t][r - l + 1] % PMOD[t] + PMOD[t]) % PMOD[t]; return ret; } // compare s[a..b] and s[c..d] O(1) bool comp(int a, int b, int c, int d) { if(a < 0 || sz <= b || c < 0 || sz <= d) return false; for(int i = 0; i < NN; i++) { if(get(a, b, i) != get(c, d, i)) return false; } return true; } // longest common extension s[l..LCE(l,r)] == s[r..LCE(l,r)] && s[l..LCE(l,r)+1] != s[r..LCE(l,r)+1] int LCE(int l,int r){ // cout<<l<<" "<<r<<endl; if(l>r) swap(l,r); // tie(l,r)=minmax(l,r); // cout<<l<<" "<<r<<endl; // if(l==5&&r==3){ // cout<<"hoge"<<endl; // cout<<"ll "<<ll<<endl; // } if(l==r) return sz-r+1; int ll = 0; int rr = sz; while(rr-ll>1){ int mid = (ll+rr)>>1; if(comp(l,l+mid-1,r,r+mid-1)) ll=mid; else rr=mid; } return ll; } }; RollingHash<ll> rh; int compare(int x, int y, int n, string &s){ if(x==-1) return 1; if(rh.comp(x, x+n-1, y, y+n-1)){ return 0; } int len = rh.LCE(x, y); // if(x==5&&y==3){ // cout<<"len "<<len<<endl; // cout<<"aa "<<s[x]<<" "<<s[y]<<endl; // } if(s[x+len]<s[y+len]) return -1; return 1; } void mainmain(){ int K; cin>>K; string s; cin>>s; if(K==0){ cout<<s<<endl; return; } K++; int n = s.size(); int m = n/K; int a = n%K; assert(n<=2000); rh.init(s); assert(a); if(a==0){ int ans = 0; rep(i,n){ int p = i*m; if(p>=n) break; if(compare(ans, p, m, s)==1) ans = p; } cout<<s.substr(ans, m)<<endl; return; } rep(i,n+1) rep(j,K+1) dp[i][j]=-1; rep(i,1,n){ if(i*m+2>=n) break; dp[i*m+1][1] = (i-1)*m; } rep(i,n){ // cout<<i<<endl; rep(j,K){ // cout<<"j "<<j<<endl; if(dp[i][j]==-1) continue; if(compare(dp[i+m][j], dp[i][j], m+1, s)==1){ dp[i+m][j] = dp[i][j]; } int p; if(dp[i][j]==-1||compare(dp[i][j], i, m+1, s)==-1) p=i; else p=dp[i][j]; // if(i==5&&j==1) cout<<"p "<<p<<" "<<dp[i+m+1][j+1]<<endl; if(compare(dp[i+m+1][j+1], p, m+1, s)==1){ dp[i+m+1][j+1] = p; } // if(i==5&&j==1) cout<<"p "<<p<<" "<<dp[i+m+1][j+1]<<endl; } } // cout<<dp[n][a]<<endl; // cout<<dp[3][1]<<endl; // cout<<dp[5][1]<<endl; // cout<<dp[8][2]<<endl; cout<<s.substr(dp[n][a],m+1)<<endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout<<fixed<<setprecision(20); mainmain(); }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | j_gui0121 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5198 Byte |
Status | RE |
Exec Time | 815 ms |
Memory | 16640 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 100 | 0 / 200 | 0 / 200 | 0 / 400 | ||||||||||||||||||||||||||||||
Status |
|
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask_02_ex1.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset1 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt |
Dataset2 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt |
Dataset3 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt |
Dataset4 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt |
Dataset5 | subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_02_01.txt, subtask_02_02.txt, subtask_02_03.txt, subtask_02_04.txt, subtask_02_05.txt, subtask_02_06.txt, subtask_02_07.txt, subtask_02_08.txt, subtask_02_09.txt, subtask_02_10.txt, subtask_02_11.txt, subtask_02_12.txt, subtask_02_13.txt, subtask_02_14.txt, subtask_02_ex1.txt, subtask_03_01.txt, subtask_03_02.txt, subtask_03_03.txt, subtask_03_04.txt, subtask_03_05.txt, subtask_03_06.txt, subtask_03_07.txt, subtask_03_08.txt, subtask_03_09.txt, subtask_03_10.txt, subtask_03_11.txt, subtask_03_12.txt, subtask_03_13.txt, subtask_03_14.txt, subtask_03_15.txt, subtask_03_ex2.txt, subtask_03_ex3.txt, subtask_04_01.txt, subtask_04_02.txt, subtask_04_03.txt, subtask_04_04.txt, subtask_04_05.txt, subtask_04_06.txt, subtask_04_07.txt, subtask_04_08.txt, subtask_04_09.txt, subtask_04_10.txt, subtask_04_11.txt, subtask_04_12.txt, subtask_04_13.txt, subtask_04_14.txt, subtask_04_15.txt, subtask_05_01.txt, subtask_05_02.txt, subtask_05_03.txt, subtask_05_04.txt, subtask_05_05.txt, subtask_05_06.txt, subtask_05_07.txt, subtask_05_08.txt, subtask_05_09.txt, subtask_05_10.txt, subtask_05_11.txt, subtask_05_12.txt, subtask_05_13.txt, subtask_05_14.txt, subtask_05_15.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 1 ms | 256 KB |
subtask_01_02.txt | RE | 102 ms | 256 KB |
subtask_01_03.txt | RE | 101 ms | 256 KB |
subtask_01_04.txt | AC | 1 ms | 256 KB |
subtask_01_05.txt | AC | 1 ms | 256 KB |
subtask_01_06.txt | AC | 1 ms | 256 KB |
subtask_01_07.txt | AC | 1 ms | 256 KB |
subtask_01_08.txt | RE | 102 ms | 256 KB |
subtask_01_09.txt | AC | 1 ms | 256 KB |
subtask_01_10.txt | AC | 1 ms | 256 KB |
subtask_01_11.txt | AC | 1 ms | 256 KB |
subtask_01_12.txt | AC | 1 ms | 256 KB |
subtask_01_13.txt | RE | 103 ms | 256 KB |
subtask_01_14.txt | AC | 1 ms | 256 KB |
subtask_01_15.txt | RE | 101 ms | 256 KB |
subtask_01_16.txt | AC | 1 ms | 256 KB |
subtask_01_17.txt | AC | 1 ms | 256 KB |
subtask_02_01.txt | RE | 102 ms | 256 KB |
subtask_02_02.txt | AC | 1 ms | 384 KB |
subtask_02_03.txt | RE | 100 ms | 256 KB |
subtask_02_04.txt | RE | 100 ms | 256 KB |
subtask_02_05.txt | AC | 1 ms | 384 KB |
subtask_02_06.txt | RE | 101 ms | 256 KB |
subtask_02_07.txt | RE | 102 ms | 256 KB |
subtask_02_08.txt | RE | 100 ms | 256 KB |
subtask_02_09.txt | AC | 2 ms | 256 KB |
subtask_02_10.txt | AC | 1 ms | 384 KB |
subtask_02_11.txt | AC | 1 ms | 384 KB |
subtask_02_12.txt | WA | 1 ms | 384 KB |
subtask_02_13.txt | RE | 100 ms | 256 KB |
subtask_02_14.txt | RE | 100 ms | 256 KB |
subtask_02_ex1.txt | AC | 1 ms | 256 KB |
subtask_03_01.txt | AC | 3 ms | 640 KB |
subtask_03_02.txt | AC | 2 ms | 640 KB |
subtask_03_03.txt | RE | 102 ms | 256 KB |
subtask_03_04.txt | RE | 99 ms | 256 KB |
subtask_03_05.txt | AC | 2 ms | 640 KB |
subtask_03_06.txt | RE | 100 ms | 256 KB |
subtask_03_07.txt | RE | 100 ms | 256 KB |
subtask_03_08.txt | RE | 101 ms | 256 KB |
subtask_03_09.txt | AC | 1 ms | 256 KB |
subtask_03_10.txt | AC | 2 ms | 640 KB |
subtask_03_11.txt | AC | 2 ms | 640 KB |
subtask_03_12.txt | AC | 2 ms | 640 KB |
subtask_03_13.txt | AC | 2 ms | 512 KB |
subtask_03_14.txt | AC | 2 ms | 640 KB |
subtask_03_15.txt | AC | 1 ms | 384 KB |
subtask_03_ex2.txt | AC | 1 ms | 256 KB |
subtask_03_ex3.txt | AC | 2 ms | 640 KB |
subtask_04_01.txt | AC | 815 ms | 16640 KB |
subtask_04_02.txt | AC | 47 ms | 16128 KB |
subtask_04_03.txt | RE | 100 ms | 384 KB |
subtask_04_04.txt | RE | 101 ms | 384 KB |
subtask_04_05.txt | AC | 296 ms | 16384 KB |
subtask_04_06.txt | RE | 100 ms | 384 KB |
subtask_04_07.txt | RE | 105 ms | 384 KB |
subtask_04_08.txt | RE | 104 ms | 384 KB |
subtask_04_09.txt | AC | 1 ms | 256 KB |
subtask_04_10.txt | AC | 142 ms | 16256 KB |
subtask_04_11.txt | AC | 136 ms | 16256 KB |
subtask_04_12.txt | AC | 89 ms | 16256 KB |
subtask_04_13.txt | AC | 4 ms | 7552 KB |
subtask_04_14.txt | AC | 25 ms | 3712 KB |
subtask_04_15.txt | AC | 46 ms | 9856 KB |
subtask_05_01.txt | RE | 101 ms | 512 KB |
subtask_05_02.txt | RE | 101 ms | 512 KB |
subtask_05_03.txt | RE | 101 ms | 512 KB |
subtask_05_04.txt | RE | 102 ms | 512 KB |
subtask_05_05.txt | RE | 101 ms | 512 KB |
subtask_05_06.txt | RE | 100 ms | 512 KB |
subtask_05_07.txt | RE | 100 ms | 512 KB |
subtask_05_08.txt | RE | 100 ms | 512 KB |
subtask_05_09.txt | AC | 2 ms | 592 KB |
subtask_05_10.txt | RE | 100 ms | 512 KB |
subtask_05_11.txt | RE | 100 ms | 512 KB |
subtask_05_12.txt | RE | 101 ms | 512 KB |
subtask_05_13.txt | RE | 101 ms | 384 KB |
subtask_05_14.txt | RE | 100 ms | 384 KB |
subtask_05_15.txt | RE | 101 ms | 384 KB |