Submission #3888367
Source Code Expand
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) for (int i = 0; i < (a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define trav(a, x) for (auto& a : x) #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define sz(x) (int)x.size() #define beg(x) x.begin() #define en(x) x.end() #define all(x) beg(x), en(x) #define resz resize const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; const ld PI = 4*atan((ld)1); template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } namespace io { // TYPE ID (StackOverflow) template<class T> struct like_array : is_array<T>{}; template<class T, size_t N> struct like_array<array<T,N>> : true_type{}; template<class T> struct like_array<vector<T>> : true_type{}; template<class T> bool is_like_array(const T& a) { return like_array<T>::value; } // I/O void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } } // INPUT template<class T> void re(T& x) { cin >> x; } template<class Arg, class... Args> void re(Arg& first, Args&... rest); void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1,T2>& p); template<class T> void re(vector<T>& a); template<class T, size_t SZ> void re(array<T,SZ>& a); template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); } template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); } template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); } template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); } template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); } // OUTPUT template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& printArray(ostream& os, const T& a, int SZ) { os << '{'; F0R(i,SZ) { if (i) { os << ", "; if (is_like_array(a[i])) cout << "\n"; } os << a[i]; } os << '}'; return os; } template<class T, size_t SZ> ostream& operator<<(ostream& os, const array<T,SZ>& a) { return printArray(os,a,SZ); } template<class T> ostream& operator<<(ostream& os, const vector<T>& a) { return printArray(os,a,sz(a)); } template<class T> ostream& operator<<(ostream& os, const set<T>& a) { os << vector<T>(all(a)); return os; } template<class T1, class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) { os << vector<pair<T1,T2>>(all(a)); return os; } template<class T> void pr(const T& x) { cout << x << '\n'; } template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { cout << first << ' '; pr(rest...); } } using namespace io; struct SuffixArray { int N; vi idx; string str; // RMQ<int,MX> R; void compress(vi& v) { vi V = v; sort(all(V)); V.erase(unique(all(V)),V.end()); for (int& i: v) i = lb(all(V),i)-V.begin()+1; } vi A, L; // A stores lexicographic value, L stores suffixes in order int get(int x) { return x >= N ? 0 : A[x]; } void sort_by(int x) { // stable sort elements in a by b vi cum(N+1); F0R(i,N) cum[get(i+x)] ++; int sum = 0; F0R(i,N+1) cum[i] = (sum += cum[i], sum-cum[i]); vi L2(N); for (int i: L) L2[cum[get(i+x)]++] = i; swap(L,L2); } void init(string _str) { str = _str; N = sz(str); A.resz(N); F0R(i,N) A[i] = str[i]; compress(A); L.resz(N); F0R(i,N) L[i] = i; for (int cnt = 1; cnt < N; cnt <<= 1) { sort_by(cnt), sort_by(0); vi A2(N); F0R(i,N) { if (i == 0) A2[L[i]] = 1; else A2[L[i]] = A2[L[i-1]]+ (mp(get(L[i]),get(L[i]+cnt)) != mp(get(L[i-1]),get(L[i-1]+cnt))); } swap(A,A2); } // vi v = lcpArray(); R.build(v); } vi lcpArray() { // KACTL int h = 0; vi inv(N), res(N); F0R(i,N) inv[L[i]] = i; F0R(i,N) if (inv[i]) { int p0 = L[inv[i] - 1]; while (max(i,p0)+h < N && str[i+h] == str[p0+h]) h++; res[inv[i]] = h; if (h) h--; } return res; } /*int lcp(int a, int b) { if (max(a,b) >= N) return 0; if (a == b) return N-a; int t0 = A[a], t1 = A[b]; if (t0 > t1) swap(t0,t1); return R.query(t0,t1-1); }*/ }; SuffixArray SA; // S.init("bcabcb"); int K,ans; string S; bool bad[100001]; bool ok() { int co = 0, cur = 0; while (co < K && cur < sz(S)) { if (bad[cur]) cur += ans-1; else cur += ans; co ++; } return cur >= sz(S); } int main() { // you should actually read the stuff at the bottom setIO(); re(K,S); K++; SA.init(S); ans = (sz(S)+K-1)/K; vi tmp = SA.L; reverse(all(tmp)); vi TMP; for (int i: tmp) if (i <= sz(S)-ans) TMP.pb(i); swap(tmp,TMP); int lo = 0, hi = sz(tmp); while (lo < hi) { int mid = (lo+hi+1)/2; F0R(i,sz(tmp)) { if (i < mid) bad[tmp[i]] = 1; else bad[tmp[i]] = 0; } if (ok()) lo = mid; else hi = mid-1; } F0R(i,ans) cout << S[tmp[lo]+i]; // pr(tmp,lo,tmp[lo]); // ans has at most ceil(S/K) digits // choose the max strings of length ceil(S/K) to decrease by 1 // you should actually read the stuff at the bottom } /* stuff you should look for * int overflow, array bounds * special cases (n=1?), set tle * do smth instead of nothing and stay organized */
Submission Info
Submission Time | |
---|---|
Task | B - Problem where Commas Separate Digits |
User | Benq |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 7336 Byte |
Status | AC |
Exec Time | 75 ms |
Memory | 2632 KB |
Compile Error
./Main.cpp: In function ‘void io::setIn(std::string)’: ./Main.cpp:67:56: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result] void setIn(string s) { freopen(s.c_str(),"r",stdin); } ^ ./Main.cpp: In function ‘void io::setOut(std::string)’: ./Main.cpp:68:58: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result] void setOut(string s) { freopen(s.c_str(),"w",stdout); } ^
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 | 256 KB |
subtask_04_02.txt | AC | 2 ms | 256 KB |
subtask_04_03.txt | AC | 2 ms | 256 KB |
subtask_04_04.txt | AC | 2 ms | 256 KB |
subtask_04_05.txt | AC | 2 ms | 256 KB |
subtask_04_06.txt | AC | 2 ms | 256 KB |
subtask_04_07.txt | AC | 2 ms | 256 KB |
subtask_04_08.txt | AC | 2 ms | 256 KB |
subtask_04_09.txt | AC | 2 ms | 256 KB |
subtask_04_10.txt | AC | 2 ms | 256 KB |
subtask_04_11.txt | AC | 2 ms | 256 KB |
subtask_04_12.txt | AC | 2 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 | 2 ms | 256 KB |
subtask_05_01.txt | AC | 75 ms | 2632 KB |
subtask_05_02.txt | AC | 74 ms | 2632 KB |
subtask_05_03.txt | AC | 75 ms | 2632 KB |
subtask_05_04.txt | AC | 72 ms | 2632 KB |
subtask_05_05.txt | AC | 72 ms | 2632 KB |
subtask_05_06.txt | AC | 72 ms | 2632 KB |
subtask_05_07.txt | AC | 71 ms | 2632 KB |
subtask_05_08.txt | AC | 70 ms | 2248 KB |
subtask_05_09.txt | AC | 69 ms | 2120 KB |
subtask_05_10.txt | AC | 65 ms | 2632 KB |
subtask_05_11.txt | AC | 31 ms | 2632 KB |
subtask_05_12.txt | AC | 31 ms | 2632 KB |
subtask_05_13.txt | AC | 50 ms | 2016 KB |
subtask_05_14.txt | AC | 65 ms | 2528 KB |
subtask_05_15.txt | AC | 23 ms | 1240 KB |