Submission #68110

#	Time	Username	Problem	Language	Result	Execution time	Memory
68110		cdemirer	Permutation Recovery (info1cup17_permutation)	C++17	43 / 100	4057 ms	252436 KiB

Main

#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 GROUP_MAX_SIZE (400)

ll N;
list<Group> L;
ll ans[70000];

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);
		}
		
		part2 = true;
	}
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	L.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;
		add(mp(a, b), i);
		
		/*for (auto it = L.begin(); it != L.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 = L.begin(); it != L.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:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < it->V.size(); i++) {
                   ~~^~~~~~~~~~~~~~
permutation.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < it->V.size(); i++) {
                    ~~^~~~~~~~~~~~~~
permutation.cpp:91:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = ptr+2; i < it->V.size(); i++) {
                        ~~^~~~~~~~~~~~~~
permutation.cpp: In function 'int main(int, char**)':
permutation.cpp:146: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++;
                   ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6