Submission #68118

#TimeUsernameProblemLanguageResultExecution timeMemory
68118cdemirerPermutation Recovery (info1cup17_permutation)C++17
10 / 100
13 ms1336 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ii> vii; typedef vector<vii> vvii; typedef pair<double, double> dodo; typedef pair<ll, ll> llp; #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define MOD1 1000000021 #define MOD2 1000000009 #define mll(x) ((((x).first)<<30)+((x).second)) ll dohash(string s, ll m) { ll ret = 0; ll ten = 1; for (int i = s.length()-1; i >= 0; i--) { ret = (ret + (s[i] - '0') * ten) % m; ten = (ten * 10) % m; } return ret; } llp operator+(const llp &a, const llp &b) { return mp((a.first + b.first) % MOD1, (a.second + b.second) % MOD2); } llp operator-(const llp &a, const llp &b) { return mp((a.first - b.first + MOD1) % MOD1, (a.second - b.second + MOD2) % MOD2); } class Group { public: vector<llp> V; vi indices; //multiset<llp> S; unordered_map<ll, ll> S; llp adjust; Group() { adjust = mp(0, 0); } }; #define SQN (250) //#define GROUP_MAX_SIZE (250) ll N; ll ans[70000]; llp table[70000]; //list<Group> L; /*void add(llp x, int ind) { bool part2 = false; for (auto it = L.begin(); it != L.end(); it++) { if (part2) { it->adjust = it->adjust - x; continue; } //cerr << "B1" << endl; //llp dbg = x - mp(1ll, 1ll) + it->adjust; //cerr << dbg.first << " " << dbg.second << endl; if (it->S.find(mll(x - mp(1ll, 1ll) + it->adjust)) == it->S.end() && x != mp(1ll, 1ll)) continue; if (it->S[mll(x - mp(1ll, 1ll) + it->adjust)] == 0 && x != mp(1ll, 1ll)) continue; //cerr << "B2" << endl; for (int i = 0; i < it->V.size(); i++) { //it->S.erase(it->S.find(it->V[i])); it->S.insert(it->V[i] - it->adjust); it->S[mll(it->V[i])]--; it->S[mll(it->V[i] - it->adjust)]++; it->V[i] = it->V[i] - it->adjust; } it->adjust = mp(0, 0); if (x == mp(1ll, 1ll)) { it->V.insert(it->V.begin(), x); //it->S.insert(x); it->S[mll(x)]++; it->indices.insert(it->indices.begin(), ind); for (int i = 1; i < it->V.size(); i++) { //it->S.erase(it->S.find(it->V[i])); it->S.insert(it->V[i] + x); it->S[mll(it->V[i])]--; it->S[mll(it->V[i] + x)]++; it->V[i] = it->V[i] + x; } } else { int ptr = 0; while (it->V[ptr] != x - mp(1ll, 1ll)) ptr++; it->V.insert(it->V.begin()+ptr+1, x+it->V[ptr]); //it->S.insert(x+it->V[ptr]); it->S[mll(x+it->V[ptr])]++; it->indices.insert(it->indices.begin()+ptr+1, ind); for (int i = ptr+2; i < it->V.size(); i++) { //it->S.erase(it->S.find(it->V[i])); it->S.insert(it->V[i] + x); it->S[mll(it->V[i])]--; it->S[mll(it->V[i] + x)]++; it->V[i] = it->V[i] + x; } } if (it->V.size() > GROUP_MAX_SIZE) { Group g; for (int i = 0; i < GROUP_MAX_SIZE/2; i++) { //it->S.erase(it->S.find(it->V[i])); it->S[mll(it->V[i])]--; //g.S.insert(it->V[i]); g.S[mll(it->V[i])]++; } for (int i = 0; i < GROUP_MAX_SIZE/2; i++) g.V.pb(it->V[i]); for (int i = 0; i < GROUP_MAX_SIZE/2; i++) g.indices.pb(it->indices[i]); it->V.erase(it->V.begin(), it->V.begin()+GROUP_MAX_SIZE/2); it->indices.erase(it->indices.begin(), it->indices.begin()+GROUP_MAX_SIZE/2); L.insert(it, g); it->S.clear(); for (int i = 0; i < it->V.size(); i++) it->S[mll(it->V[i])]++; } part2 = true; } }*/ vector<Group> LST; void add(llp x, int ind) { //cerr << "A" << endl; llp toadd = mp(0ll, 0ll); for (int i = 0; i < LST.size(); i++) { if (toadd != mp(0ll, 0ll)) LST[i].adjust = LST[i].adjust - toadd; else if (LST[i].S[mll(x - mp(1ll, 1ll) + LST[i].adjust)] || (i==0 && x == mp(1ll, 1ll))) { //cerr << "B" << endl; if (LST[i].adjust != mp(0ll, 0ll)) { for (int j = 0; j < LST[i].V.size(); j++) { LST[i].S[mll(LST[i].V[j])]--; LST[i].S[mll(LST[i].V[j]+x)]++; LST[i].V[j] = LST[i].V[j] - LST[i].adjust; } LST[i].adjust = mp(0, 0); } int ptr = 0; llp xadd = mp(0, 0); if (x != mp(1ll, 1ll)) { while (LST[i].V[ptr] != x - mp(1ll, 1ll)) ptr++; ptr++; xadd = LST[i].V[ptr-1]; } LST[i].V.insert(LST[i].V.begin()+ptr, x + xadd); LST[i].S[mll(x + xadd)]++; LST[i].indices.insert(LST[i].indices.begin()+ptr, ind); for (int j = ptr+1; j < LST[i].V.size(); j++) { LST[i].S[mll(LST[i].V[j])]--; LST[i].S[mll(LST[i].V[j] + x)]++; LST[i].V[j] = LST[i].V[j] + x; } toadd = x; } } } void tidyup() { vi I; for (int i = 0; i < LST.size(); i++) { for (int j = 0; j < LST[i].V.size(); j++) { I.pb( LST[i].indices[j] ); } } LST.clear(); LST.resize(I.size()/SQN+1); for (int i = 0; i < I.size(); i++) { LST[i/SQN].V.pb(table[I[i]]); LST[i/SQN].indices.pb(I[i]); } for (int i = 0; i < LST.size(); i++) { if (LST[i].V.size() == 0) continue; if (i > 0) LST[i].V[0] = LST[i].V[0] + LST[i-1].V[LST[i-1].V.size()-1]; LST[i].S[mll(LST[i].V[0])]++; for (int j = 1; j < LST[i].V.size(); j++) { LST[i].V[j] = LST[i].V[j] + LST[i].V[j-1]; LST[i].S[mll(LST[i].V[j])]++; } } //cerr << I.size() << " things..." << endl; } int main(int argc, char **argv) { ios_base::sync_with_stdio(0); cin.tie(0); LST.push_back(Group()); cin >> N; ll lasta = 0, lastb = 0; for (int i = 0; i < N; i++) { string s; cin >> s; ll a = (dohash(s, MOD1) - lasta + MOD1) % MOD1; ll b = (dohash(s, MOD2) - lastb + MOD2) % MOD2; //cerr << "a: " << a << " b: " << b << endl; //cerr << "lasta: " << lasta << " lastb: " << lastb << endl; lasta = (lasta + a) % MOD1, lastb = (lastb + b) % MOD2; table[i] = mp(a, b); add(mp(a, b), i); if (i % SQN == 0) { tidyup(); //cerr << "DID TIDY" << endl; } /*for (auto it = LST.begin(); it != LST.end(); it++) { cerr << "a group: " << it->V.size() << "\n"; for (int k = 0; k < it->indices.size(); k++) { cerr << (it->V[k]-it->adjust).first << " " << it->indices[k] << " \n"; } for (auto x : it->S) { cerr << ": " << x.first << " "; } cerr << endl; }*/ } int cnt = 0; for (auto it = LST.begin(); it != LST.end(); it++) { for (int k = 0; k < it->indices.size(); k++) ans[it->indices[k]] = cnt++; } for (int i = 0; i < N; i++) cout << ans[i]+1 << " "; cout << '\n'; return 0; }

Compilation message (stderr)

permutation.cpp: In function 'void add(llp, int)':
permutation.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < LST[i].V.size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~
permutation.cpp:146:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = ptr+1; j < LST[i].V.size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~
permutation.cpp: In function 'void tidyup()':
permutation.cpp:157:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:158:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < LST[i].V.size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~
permutation.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:172:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < LST[i].V.size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~
permutation.cpp: In function 'int main(int, char**)':
permutation.cpp:215:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k = 0; k < it->indices.size(); k++) ans[it->indices[k]] = cnt++;
                   ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...