oj.uz

Submission #68224

# Submission time Handle Problem Language Result Execution time Memory
68224 2018-08-16T09:01:08 Z cdemirer Permutation Recovery (info1cup17_permutation) C++17
43 / 100
 4000 ms 84280 KB 
#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 1000000007

#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;
	unordered_map<ll, ll> S;
	llp adjust;
	Group() {
		adjust = mp(0, 0);
	}
};

#define SQN (200)

ll N;
ll ans[70000];
llp table[70000];

bool shouldTidy = false;
vector<Group> LST;
void add(llp x, int ind) {
	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))) {
			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] - LST[i].adjust)]++;
					LST[i].V[j] = LST[i].V[j] - LST[i].adjust;
					assert(LST[i].V[j].first >= 0);
					assert(LST[i].V[j].second >= 0);
				}
				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);
			assert((x + xadd).first >= 0);
			assert((x + xadd).second >= 0);
			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;
				assert(LST[i].V[j].first >= 0);
				assert(LST[i].V[j].second >= 0);
			}
			toadd = x;
		}
		if (LST[i].indices.size() >= SQN*3/2) shouldTidy = true;
	}
	if (toadd == mp(0ll, 0ll)) {
		cerr << "ERROR" << endl;
		cerr << "COULD NOT INSERT VALUE" << endl;
		cerr << "ERROR" << endl;
	}
}

void tidyup() {
	vi I;
	for (int i = 0; i < LST.size(); i++) {
		for (int j = 0; j < LST[i].indices.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.back();
		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])]++;
		}
	}
	shouldTidy = false;
}

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 << i+1 << " / " << N << endl;
//cerr << "a: " << a << "   b: " << b << "  i:" << i << 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 (shouldTidy) {
			tidyup();
//cerr << "DID TIDY" << endl;
		}
		
		/*for (auto it = LST.begin(); it != LST.end(); it++) {
			cerr << "a group: " << it->V.size() << "..." << it->adjust.first << "\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;
		}*/
		
	}
	//cerr << N << endl;
	int cnt = 0;
	for (auto lst : LST) for (auto k : lst.indices) ans[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:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < LST[i].V.size(); j++) {
                     ~~^~~~~~~~~~~~~~~~~
permutation.cpp:80: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:99:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < LST[i].indices.size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < I.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < LST.size(); i++) {
                  ~~^~~~~~~~~~~~
permutation.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < LST[i].V.size(); j++) {
                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct
5 Execution timed out 4086 ms 84280 KB Time limit exceeded

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct
5 Execution timed out 4086 ms 84280 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct
5 Execution timed out 4086 ms 84280 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct
5 Execution timed out 4086 ms 84280 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 16 ms 1288 KB Output is correct
3 Correct 21 ms 1288 KB Output is correct
4 Correct 4 ms 1288 KB Output is correct
5 Execution timed out 4086 ms 84280 KB Time limit exceeded