Submission #3878660
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl #define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl #define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl #define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl #define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; string s; int n, K, keta; bool comp(string& a, string& b) { if(len(a) < len(b)){ return true; }else if(len(a) > len(b)){ return false; }else{ return a < b; } } bool possible(string& t) { string nw; int cnt = 0; rep(i,n){ nw.pb(s[i]); if(comp(t, nw)){ nw.clear(); cnt++; nw.pb(s[i]); if(comp(t, nw)){ return false; } } } return (cnt <= K); } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> K; cin >> s; n = len(s); keta = (n+K) / (K+1); if(K == 0){ cout << s << "\n"; return 0; } if(K == 1){ string x = s.substr(0,keta), y = s.substr(n-keta,keta); if(comp(x, y)){ cout << y << "\n"; }else{ cout << x << "\n"; } return 0; } vs ss; rep(i,n-keta+1){ ss.pb(s.substr(i,keta)); } sort(all(ss),comp); int l = -1, r = n-keta; while(r-l>1){ int mid = (l+r)/2; if(possible(ss[mid])){ r = mid; }else{ l = mid; } } cout << ss[r] << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | kopricky |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2701 Byte |
Status | AC |
Exec Time | 65 ms |
Memory | 5828 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 | 2 ms | 384 KB |
subtask_04_02.txt | AC | 2 ms | 384 KB |
subtask_04_03.txt | AC | 2 ms | 384 KB |
subtask_04_04.txt | AC | 2 ms | 384 KB |
subtask_04_05.txt | AC | 2 ms | 384 KB |
subtask_04_06.txt | AC | 2 ms | 384 KB |
subtask_04_07.txt | AC | 2 ms | 384 KB |
subtask_04_08.txt | AC | 1 ms | 256 KB |
subtask_04_09.txt | AC | 1 ms | 256 KB |
subtask_04_10.txt | AC | 2 ms | 384 KB |
subtask_04_11.txt | AC | 2 ms | 384 KB |
subtask_04_12.txt | AC | 2 ms | 384 KB |
subtask_04_13.txt | AC | 2 ms | 384 KB |
subtask_04_14.txt | AC | 1 ms | 256 KB |
subtask_04_15.txt | AC | 2 ms | 384 KB |
subtask_05_01.txt | AC | 65 ms | 5828 KB |
subtask_05_02.txt | AC | 64 ms | 5828 KB |
subtask_05_03.txt | AC | 40 ms | 5828 KB |
subtask_05_04.txt | AC | 53 ms | 5828 KB |
subtask_05_05.txt | AC | 53 ms | 5828 KB |
subtask_05_06.txt | AC | 56 ms | 5828 KB |
subtask_05_07.txt | AC | 59 ms | 5828 KB |
subtask_05_08.txt | AC | 2 ms | 592 KB |
subtask_05_09.txt | AC | 2 ms | 592 KB |
subtask_05_10.txt | AC | 45 ms | 5828 KB |
subtask_05_11.txt | AC | 37 ms | 5828 KB |
subtask_05_12.txt | AC | 37 ms | 5828 KB |
subtask_05_13.txt | AC | 46 ms | 4472 KB |
subtask_05_14.txt | AC | 58 ms | 5492 KB |
subtask_05_15.txt | AC | 23 ms | 2552 KB |