Submission #998729
Source Code Expand
#include <bits/stdc++.h> #include <assert.h> using namespace std; typedef long long ll; typedef long double ld; #define PB push_back #define MP make_pair #define MOD 1000000007LL #define endl "\n" const ll UNDEF = -1; const ll INF=1e18; template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; } template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; } typedef pair<ll,ll> pll; #ifdef DEBUG #define debug(args...) {dbg,args; cerr<<endl;} #else #define debug(args...) // Just strip off all debug tokens #endif struct debugger { template<typename T> debugger& operator , (const T& v) { cerr<<v<<" "; return *this; } } dbg; ll k; string s; bool cmp(pll a, pll b) { ll an=a.second-a.first,bn=b.second-b.first; if (an<bn) return true; if (an>bn) return false; for (ll i=0;i<an;i++) { if (s[a.first+i]<s[b.first+i]) return true; if (s[a.first+i]>s[b.first+i]) return false; } return false; } string go(ll x, ll y) { return s.substr(x,y-x); } bool leq(pll a, pll b) { ll an=a.second-a.first,bn=b.second-b.first; if (an<bn) return true; if (an>bn) return false; for (ll i=0;i<an;i++) { //cout<<s[a.first+i]<<s[b.first+i]<<endl; if (s[a.first+i]<s[b.first+i]) return true; if (s[a.first+i]>s[b.first+i]) return false; } return true; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>k>>s; ll n=s.length(); ll q=max(1LL,n/(k+1)); vector<pll> v; for (ll i=0;i<n;i++) { if (i+q<=n) v.PB(MP(i,i+q)); if (i+q+1<=n) v.PB(MP(i,i+q+1)); } //cout<<q<<endl; sort(v.begin(),v.end(),cmp); for (ll i=0;i<v.size();i++) { ll imid=i; //cout<<"i:"<<i<<":"<<go(v[imid].first,v[imid].second)<<endl; } ll imin=0,imax=v.size(); while(imin<imax) { ll imid=(imin+imax)/2; //cout<<"imid"<<go(v[imid].first,v[imid].second)<<endl; ll x=0; bool ok=true; for (ll i=0;i<k+1;i++) { //cout<<go(x,min(x+q+1,n))<<"<=ISA?"<<go(v[imid].first,v[imid].second); if (leq(MP(x,min(x+q+1,n)),v[imid])) { //cout<<go(x,min(x+q+1,n))<<"<=A"<<go(v[imid].first,v[imid].second); x=min(x+q+1,n); } else if (leq(MP(x,min(x+q,n)),v[imid])) { //cout<<go(x,min(x+q,n))<<"<=B"<<go(v[imid].first,v[imid].second); x=min(x+q,n); } else { ok=false; break; } //cout<<x<<endl; } if (ok&&x==n) { imax=imid; } else { imin=imid+1; } } { ll x=v[imin].first,y=v[imin].second; cout<<s.substr(x,y-x)<<endl; } }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | LiChenKoh |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2633 Byte |
Status | AC |
Exec Time | 67 ms |
Memory | 4592 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | Dataset3 | Dataset4 | Dataset5 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 100 / 100 | 200 / 200 | 200 / 200 | 400 / 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 | 3 ms | 256 KB |
subtask_01_02.txt | AC | 3 ms | 256 KB |
subtask_01_03.txt | AC | 3 ms | 256 KB |
subtask_01_04.txt | AC | 3 ms | 256 KB |
subtask_01_05.txt | AC | 3 ms | 256 KB |
subtask_01_06.txt | AC | 3 ms | 256 KB |
subtask_01_07.txt | AC | 3 ms | 256 KB |
subtask_01_08.txt | AC | 3 ms | 256 KB |
subtask_01_09.txt | AC | 2 ms | 256 KB |
subtask_01_10.txt | AC | 3 ms | 256 KB |
subtask_01_11.txt | AC | 3 ms | 256 KB |
subtask_01_12.txt | AC | 3 ms | 256 KB |
subtask_01_13.txt | AC | 3 ms | 256 KB |
subtask_01_14.txt | AC | 3 ms | 256 KB |
subtask_01_15.txt | AC | 3 ms | 256 KB |
subtask_01_16.txt | AC | 3 ms | 256 KB |
subtask_01_17.txt | AC | 3 ms | 256 KB |
subtask_02_01.txt | AC | 3 ms | 256 KB |
subtask_02_02.txt | AC | 3 ms | 256 KB |
subtask_02_03.txt | AC | 3 ms | 256 KB |
subtask_02_04.txt | AC | 3 ms | 256 KB |
subtask_02_05.txt | AC | 3 ms | 256 KB |
subtask_02_06.txt | AC | 3 ms | 256 KB |
subtask_02_07.txt | AC | 3 ms | 256 KB |
subtask_02_08.txt | AC | 3 ms | 256 KB |
subtask_02_09.txt | AC | 3 ms | 256 KB |
subtask_02_10.txt | AC | 3 ms | 256 KB |
subtask_02_11.txt | AC | 3 ms | 256 KB |
subtask_02_12.txt | AC | 3 ms | 256 KB |
subtask_02_13.txt | AC | 3 ms | 256 KB |
subtask_02_14.txt | AC | 3 ms | 256 KB |
subtask_02_ex1.txt | AC | 3 ms | 256 KB |
subtask_03_01.txt | AC | 3 ms | 256 KB |
subtask_03_02.txt | AC | 3 ms | 256 KB |
subtask_03_03.txt | AC | 3 ms | 256 KB |
subtask_03_04.txt | AC | 3 ms | 256 KB |
subtask_03_05.txt | AC | 3 ms | 256 KB |
subtask_03_06.txt | AC | 3 ms | 256 KB |
subtask_03_07.txt | AC | 3 ms | 256 KB |
subtask_03_08.txt | AC | 3 ms | 256 KB |
subtask_03_09.txt | AC | 3 ms | 256 KB |
subtask_03_10.txt | AC | 3 ms | 256 KB |
subtask_03_11.txt | AC | 3 ms | 256 KB |
subtask_03_12.txt | AC | 3 ms | 256 KB |
subtask_03_13.txt | AC | 3 ms | 256 KB |
subtask_03_14.txt | AC | 3 ms | 256 KB |
subtask_03_15.txt | AC | 3 ms | 256 KB |
subtask_03_ex2.txt | AC | 3 ms | 256 KB |
subtask_03_ex3.txt | AC | 3 ms | 256 KB |
subtask_04_01.txt | AC | 3 ms | 384 KB |
subtask_04_02.txt | AC | 3 ms | 384 KB |
subtask_04_03.txt | AC | 3 ms | 384 KB |
subtask_04_04.txt | AC | 3 ms | 384 KB |
subtask_04_05.txt | AC | 3 ms | 384 KB |
subtask_04_06.txt | AC | 3 ms | 384 KB |
subtask_04_07.txt | AC | 3 ms | 384 KB |
subtask_04_08.txt | AC | 3 ms | 384 KB |
subtask_04_09.txt | AC | 3 ms | 256 KB |
subtask_04_10.txt | AC | 3 ms | 384 KB |
subtask_04_11.txt | AC | 3 ms | 384 KB |
subtask_04_12.txt | AC | 3 ms | 384 KB |
subtask_04_13.txt | AC | 3 ms | 384 KB |
subtask_04_14.txt | AC | 3 ms | 256 KB |
subtask_04_15.txt | AC | 3 ms | 384 KB |
subtask_05_01.txt | AC | 51 ms | 4544 KB |
subtask_05_02.txt | AC | 51 ms | 4544 KB |
subtask_05_03.txt | AC | 48 ms | 4544 KB |
subtask_05_04.txt | AC | 47 ms | 4544 KB |
subtask_05_05.txt | AC | 50 ms | 4544 KB |
subtask_05_06.txt | AC | 63 ms | 4544 KB |
subtask_05_07.txt | AC | 67 ms | 4544 KB |
subtask_05_08.txt | AC | 33 ms | 2500 KB |
subtask_05_09.txt | AC | 3 ms | 592 KB |
subtask_05_10.txt | AC | 50 ms | 4544 KB |
subtask_05_11.txt | AC | 40 ms | 4544 KB |
subtask_05_12.txt | AC | 40 ms | 4544 KB |
subtask_05_13.txt | AC | 52 ms | 4592 KB |
subtask_05_14.txt | AC | 64 ms | 4592 KB |
subtask_05_15.txt | AC | 29 ms | 2584 KB |