Submission #129396

#	Time	Username	Problem	Language	Result	Execution time	Memory
129396		E869120	Permutation Recovery (info1cup17_permutation)	C++14	60 / 100	4011 ms	7456 KiB

Main

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;

// ------------------ LIBRARY --------------------

const long long mod = 869120869120869120LL;
const long long mod2 = 777777777777777777LL;

const int BACKET = 100;
long long t[1 << 17], u[1 << 17], size_;
set<pair<long long, int>> Set[1 << 13];

void init(vector<long long>E) {
	size_ = E.size() + 1;
	for (int i = 1; i <= E.size(); i++) {
		t[i] = E[i - 1];
		Set[i / BACKET].insert(make_pair(t[i], i));
	}
}

void add_range(int l, int r, long long x) {
	int c = l / BACKET;
	for (int i = l; i < r; i++) {
		Set[c].erase(make_pair(t[i], i));
		t[i] += x; t[i] %= mod;
		Set[c].insert(make_pair(t[i], i));
	}
}

void add(int l, int r, long long x) {
	x = (x + mod) % mod;

	int c1 = l / BACKET, c2 = r / BACKET;
	if (c1 == c2) add_range(l, r, x);
	else {
		add_range(l, (c1 + 1) * BACKET, x);
		add_range(c2 * BACKET, r, x);
		for (int i = c1 + 1; i < c2; i++) {
			u[i] += x; u[i] %= mod;
		}
	}
}

int get_minimum_id() {
	int id = -1;
	for (int i = size_ / BACKET; i >= 0; i--) {
		long long T = (mod + 1LL - u[i]) % mod;
		auto itr = Set[i].lower_bound(make_pair(T + 1LL, 0));
		if (itr != Set[i].begin()) {
			itr--;
			if ((*itr).first == T) { id = (*itr).second; break; }
		}
	}
	return id;
}

long long StringToMod(string S) {
	long long r = 0;
	for (int i = 0; i < S.size(); i++) {
		r *= 10LL; r += (long long)(S[i] - '0');
		r %= mod;
	}
	return r;
}

long long N, A[1 << 18], S[1 << 18];
vector<long long>F;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		string V; cin >> V;
		A[i] = StringToMod(V);
	}
	for (int i = N; i >= 1; i--) A[i] = (A[i] - A[i - 1] + mod) % mod;
	for (int i = 1; i <= N; i++) F.push_back(A[i]);

	init(F);

	for (int i = 1; i <= N; i++) {
		int pos1 = get_minimum_id();
		S[pos1] = i;
		add(pos1 + 1, N + 1, -A[pos1]);
		add(pos1, pos1 + 1, mod2);
	}
	for (int i = 1; i <= N; i++) { if (i >= 2) cout << " "; cout << S[i]; } cout << endl;
	return 0;
}

Compilation message (stderr)

permutation.cpp: In function 'void init(std::vector<long long int>)':
permutation.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= E.size(); i++) {
                  ~~^~~~~~~~~~~
permutation.cpp: In function 'long long int StringToMod(std::__cxx11::string)':
permutation.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~

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