oj.uz

Submission #129430

# Submission time Handle Problem Language Result Execution time Memory
129430 2019-07-12T08:42:57 Z E869120 Permutation Recovery (info1cup17_permutation) C++14
78 / 100
 4000 ms 6744 KB 
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;
#pragma warning (disable: 4996)

int cnta = 0, cntb = 0;

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

const long long mod = 869120869120LL;
const long long mod2 = 777777777777LL;

const int BACKET = 150;
long long t[1 << 17], u[1 << 17], size_;
set<long long> Set[1 << 13];
bool used[1 << 17];

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(131072LL * t[i] + 1LL * i);
	}
}

void add_range(int l, int r, long long x) {
	int c = l / BACKET;
	for (int i = l; i < r; i++) {
		if (used[i] == true) continue;
		Set[c].erase(131072LL * t[i] + 1LL * i); cnta++;
		t[i] += x; if (t[i] >= mod) t[i] -= mod;
		Set[c].insert(131072LL * t[i] + 1LL * i); cnta++;
	}
}

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);
		for (int i = c1 + 1; i <= c2; i++) {
			u[i] += x; if (u[i] >= mod) 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]); if (T >= mod) T -= mod;
		auto itr = Set[i].lower_bound(131072LL * (T + 1LL)); cntb++;
		if (itr != Set[i].begin()) {
			itr--;
			if (((*itr) >> 17) == T) { id = ((*itr) & 131071LL); break; }
		}
	}
	return id;
}

void annihilation(int pos) {
	Set[pos / BACKET].erase(131072LL * t[pos] + 1LL * pos);
	used[pos] = true;
}

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');
		while (r >= mod) r -= mod;
	}
	return r;
}

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

int main() {
	//FILE *in = freopen("in9.txt", "r", stdin);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%s", &cc); string V = "";
		for (int j = 0; j < 100000; j++) {
			if (cc[j] == 0) break;
			V += cc[j]; cc[j] = 0;
		}
		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]);
		annihilation(pos1);
	}
	for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n");
	return 0;
}

Compilation message

permutation.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
permutation.cpp: In function 'void init(std::vector<long long int>)':
permutation.cpp:23: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:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:86:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[262144]' [-Wformat=]
   scanf("%s", &cc); string V = "";
               ~~~^
permutation.cpp:104:75: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", S[i]); } printf("\n");
                                                                       ~~~~^
permutation.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &cc); string V = "";
   ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct
5 Correct 1077 ms 4100 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct
5 Correct 1077 ms 4100 KB Output is correct
6 Correct 2579 ms 6744 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct
5 Correct 1077 ms 4100 KB Output is correct
6 Correct 2579 ms 6744 KB Output is correct
7 Correct 3227 ms 6744 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct
5 Correct 1077 ms 4100 KB Output is correct
6 Correct 2579 ms 6744 KB Output is correct
7 Correct 3227 ms 6744 KB Output is correct
8 Correct 2770 ms 3120 KB Output is correct
9 Execution timed out 4048 ms 6416 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 18 ms 760 KB Output is correct
4 Correct 14 ms 760 KB Output is correct
5 Correct 1077 ms 4100 KB Output is correct
6 Correct 2579 ms 6744 KB Output is correct
7 Correct 3227 ms 6744 KB Output is correct
8 Correct 2770 ms 3120 KB Output is correct
9 Execution timed out 4048 ms 6416 KB Time limit exceeded