#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
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 time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
1336 KB |
Output isn't correct |
