Submission #1721045
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<int>::iterator sit; typedef map<int,int>::iterator mit; typedef vector<int>::iterator vit; string s; bool used[100001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int k; cin>>k>>s; int n = int(s.length()); int d = (n/(k+1)); int u = d + 1; int rem = n%(k+1); //rem times of u //cerr<<n<<'\n'; if(rem == 0) { string ans; for(int j = 0; j < d; j++) { int tmp = 1; for(int i = 0; i < n; i += d) { if(used[i]) continue; if(s[i+j]-'0'>tmp) { tmp=s[i+j]-'0'; } } for(int i = 0; i < n; i += d) { if(used[i]) continue; if(s[i+j]-'0'<tmp) { used[i]=true; } } ans+=char(tmp+'0'); } cout<<ans<<'\n'; return 0; } string ans; for(int i = 0; i < u; i++) //BS each digit { int lo = 1; int hi = 9; int an = 0; while(lo<=hi) { int mid = (lo+hi)>>1; int j = 0; int cnt = rem; //cerr<<cnt<<' '<<u<<'\n'; while(cnt>0&&j<n) { //cerr<<j<<' '<<cnt<<' '<<mid<<'\n'; if(j+u>n) break; bool pos = true; for(int k = j; k < j + u; k++) { if(k-j>i) { break; } else if(k-j==i) { if(s[k]-'0'<=mid) { break; } else { pos=false; break; } } else { if(s[k]>ans[k-j]) { pos=false; break; } else if(s[k]<ans[k-j]) { break; } } } if(pos) { cnt--; j+=u; } else { j+=d; } } //cerr<<i<<' '<<mid<<' '<<cnt<<'\n'; if(cnt==0) { an=mid; hi=mid-1; } else { lo=mid+1; } } ans += char(an+'0'); } cout<<ans<<'\n'; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | vjudge1 |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2151 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 720 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 | 1 ms | 256 KB |
subtask_01_02.txt | AC | 1 ms | 256 KB |
subtask_01_03.txt | AC | 1 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 | AC | 1 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 | AC | 1 ms | 256 KB |
subtask_01_14.txt | AC | 1 ms | 256 KB |
subtask_01_15.txt | AC | 1 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 | AC | 1 ms | 256 KB |
subtask_02_02.txt | AC | 1 ms | 256 KB |
subtask_02_03.txt | AC | 1 ms | 256 KB |
subtask_02_04.txt | AC | 1 ms | 256 KB |
subtask_02_05.txt | AC | 1 ms | 256 KB |
subtask_02_06.txt | AC | 1 ms | 256 KB |
subtask_02_07.txt | AC | 1 ms | 256 KB |
subtask_02_08.txt | AC | 1 ms | 256 KB |
subtask_02_09.txt | AC | 1 ms | 256 KB |
subtask_02_10.txt | AC | 1 ms | 256 KB |
subtask_02_11.txt | AC | 1 ms | 256 KB |
subtask_02_12.txt | AC | 1 ms | 256 KB |
subtask_02_13.txt | AC | 1 ms | 256 KB |
subtask_02_14.txt | AC | 1 ms | 256 KB |
subtask_02_ex1.txt | AC | 1 ms | 256 KB |
subtask_03_01.txt | AC | 1 ms | 256 KB |
subtask_03_02.txt | AC | 1 ms | 256 KB |
subtask_03_03.txt | AC | 1 ms | 256 KB |
subtask_03_04.txt | AC | 1 ms | 256 KB |
subtask_03_05.txt | AC | 1 ms | 256 KB |
subtask_03_06.txt | AC | 1 ms | 256 KB |
subtask_03_07.txt | AC | 1 ms | 256 KB |
subtask_03_08.txt | AC | 1 ms | 256 KB |
subtask_03_09.txt | AC | 1 ms | 256 KB |
subtask_03_10.txt | AC | 1 ms | 256 KB |
subtask_03_11.txt | AC | 1 ms | 256 KB |
subtask_03_12.txt | AC | 1 ms | 256 KB |
subtask_03_13.txt | AC | 1 ms | 256 KB |
subtask_03_14.txt | AC | 1 ms | 256 KB |
subtask_03_15.txt | AC | 1 ms | 256 KB |
subtask_03_ex2.txt | AC | 1 ms | 256 KB |
subtask_03_ex3.txt | AC | 1 ms | 256 KB |
subtask_04_01.txt | AC | 1 ms | 256 KB |
subtask_04_02.txt | AC | 1 ms | 256 KB |
subtask_04_03.txt | AC | 1 ms | 256 KB |
subtask_04_04.txt | AC | 1 ms | 256 KB |
subtask_04_05.txt | AC | 1 ms | 256 KB |
subtask_04_06.txt | AC | 1 ms | 256 KB |
subtask_04_07.txt | AC | 1 ms | 256 KB |
subtask_04_08.txt | AC | 1 ms | 256 KB |
subtask_04_09.txt | AC | 1 ms | 256 KB |
subtask_04_10.txt | AC | 1 ms | 256 KB |
subtask_04_11.txt | AC | 1 ms | 256 KB |
subtask_04_12.txt | AC | 1 ms | 256 KB |
subtask_04_13.txt | AC | 1 ms | 256 KB |
subtask_04_14.txt | AC | 1 ms | 256 KB |
subtask_04_15.txt | AC | 1 ms | 256 KB |
subtask_05_01.txt | AC | 3 ms | 512 KB |
subtask_05_02.txt | AC | 5 ms | 512 KB |
subtask_05_03.txt | AC | 2 ms | 592 KB |
subtask_05_04.txt | AC | 2 ms | 592 KB |
subtask_05_05.txt | AC | 4 ms | 512 KB |
subtask_05_06.txt | AC | 2 ms | 592 KB |
subtask_05_07.txt | AC | 2 ms | 592 KB |
subtask_05_08.txt | AC | 2 ms | 592 KB |
subtask_05_09.txt | AC | 2 ms | 720 KB |
subtask_05_10.txt | AC | 5 ms | 512 KB |
subtask_05_11.txt | AC | 4 ms | 512 KB |
subtask_05_12.txt | AC | 4 ms | 512 KB |
subtask_05_13.txt | AC | 4 ms | 384 KB |
subtask_05_14.txt | AC | 4 ms | 384 KB |
subtask_05_15.txt | AC | 3 ms | 384 KB |