Submission #129263

#	Time	Username	Problem	Language	Result	Execution time	Memory
129263		E869120	Permutation Recovery (info1cup17_permutation)	C++14	60 / 100	1527 ms	47492 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#pragma warning (disable: 4996)

int cnt = 0;

const long long MAX_Z = 1000000000000000000LL;
 
struct BigInteger {
	long long t[25]; int sz;
};
 
bool operator==(BigInteger a1, BigInteger a2) {
	if (a1.sz == a2.sz) return true;
	return false;
}
 
bool operator<(BigInteger a1, BigInteger a2) {
	if (a1.sz < a2.sz) return true;
	if (a1.sz > a2.sz) return false;
	for (int i = (int)a1.sz - 1; i >= 0; i--) {
		if (a1.t[i] < a2.t[i]) return true;
		if (a1.t[i] > a2.t[i]) return false;
	}
	return false;
}
 
BigInteger operator+(BigInteger a1, BigInteger a2) {
	BigInteger a3; for (int i = 0; i <= max(a1.sz, a2.sz); i++) a3.t[i] = 0;
	a3.sz = max(a1.sz, a2.sz) + 1;
	
	for (int i = 0; i < a1.sz; i++) a3.t[i] += a1.t[i];
	for (int i = 0; i < a2.sz; i++) a3.t[i] += a2.t[i];
	for (int i = 0; i < (int)a3.sz - 1; i++) {
		while (a3.t[i] >= MAX_Z) { a3.t[i] -= MAX_Z; a3.t[i + 1] += 1; }
	}
	while (a3.sz >= 2 && a3.t[a3.sz - 1] == 0) a3.sz--;
	return a3;
}
 
BigInteger operator-(BigInteger a1, BigInteger a2) {
	BigInteger a3; for (int i = 0; i <= max(a1.sz, a2.sz); i++) a3.t[i] = 0;
	a3.sz = max(a1.sz, a2.sz) + 1;
	
	for (int i = 0; i < a1.sz; i++) a3.t[i] += a1.t[i];
	for (int i = 0; i < a2.sz; i++) a3.t[i] -= a2.t[i];
	for (int i = 0; i < (int)a3.sz - 1; i++) {
		while (a3.t[i] < 0) { a3.t[i] += MAX_Z; a3.t[i + 1] -= 1; }
	}
	while (a3.sz >= 2 && a3.t[a3.sz - 1] == 0) a3.sz--;
	return a3;
}
 
BigInteger ConvertFromString(string V) {
	BigInteger a1; for (int i = 0; i < (int)(V.size() + 17) / 18; i++) a1.t[i] = 0;
	a1.sz = (int)(V.size() + 17) / 18;
	reverse(V.begin(), V.end());
	
	long long r = 1;
	for (int i = 0; i < V.size(); i++) {
		a1.t[i / 18] += r * (long long)(V[i] - '0');
		r *= 10;
		if (i % 18 == 17) r = 1;
	}
	return a1;
}
 
BigInteger getmin(BigInteger a1, BigInteger a2) {
	if (a1.t < a2.t) return a1;
	return a2;
}
 
pair<BigInteger, int> getmin(pair<BigInteger, int> a1, pair<BigInteger, int> a2) {
	if (a1.first < a2.first) return a1;
	return a2;
}
 
int N;
BigInteger P[100009]; int A[100009];
char cc[100009];
 
// -------------------- Segment Tree -------------------
 
int size_ = 0;
pair<BigInteger, int> dat[1 << 17]; BigInteger lazy[1 << 17]; BigInteger INF;
 
void init(int sz) {
	string str = ""; for (int i = 0; i < 220; i++) str += "9";
	INF = ConvertFromString(str);
 
	size_ = 1;
	while (size_ <= sz) size_ *= 2;
 
	for (int i = 1; i <= N; i++) dat[size_ + i] = make_pair(P[i], i);
	for (int i = size_ - 1; i >= 1; i--) dat[i] = getmin(dat[i * 2], dat[i * 2 + 1]);
}

void move_lazy(int pos) {
	if (pos < size_) {
		lazy[pos * 2 + 0] = lazy[pos * 2 + 0] + lazy[pos];
		lazy[pos * 2 + 1] = lazy[pos * 2 + 1] + lazy[pos];
		lazy[pos] = ConvertFromString("0");
	}
}

void refresh(int pos) {
	if (pos < size_) {
		pair<BigInteger, int> A1 = dat[pos * 2 + 0]; A1.first = A1.first - lazy[pos * 2 + 0];
		pair<BigInteger, int> A2 = dat[pos * 2 + 1]; A2.first = A2.first - lazy[pos * 2 + 1];
		dat[pos] = getmin(A1, A2);
	}
	else {
		pair<BigInteger, int> A1 = dat[pos]; A1.first = A1.first - lazy[pos];
		lazy[pos] = ConvertFromString("0");
		dat[pos] = A1;
	}
}
 
void lose_(int l, int r, BigInteger p, int a, int b, int u) {
	if (l <= a && b <= r) { lazy[u] = lazy[u] + p; move_lazy(u); refresh(u); return; }
	if (r <= a || b <= l) return;
	
	lose_(l, r, p, a, (a + b) >> 1, u * 2 + 0);
	lose_(l, r, p, (a + b) >> 1, b, u * 2 + 1);
	refresh(u);
}
 
void lose(int cl, int cr, BigInteger p) {
	lose_(cl, cr, p, 0, size_, 1);
}
 
pair<BigInteger, int> query_(int l, int r, int a, int b, int u) {
	move_lazy(u);
	if (l <= a && b <= r) return dat[u];
	if (r <= a || b <= l) return make_pair(INF, -1);
 
	pair<BigInteger, int> G1 = query_(l, r, a, (a + b) >> 1, u * 2 + 0);
	pair<BigInteger, int> G2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
	refresh(u);
	return getmin(G1, G2);
}
 
pair<BigInteger, int> query(int l, int r) {
	return query_(l, r, 0, size_, 1);
}
 
void annihilation(int pos) {
	dat[pos + size_] = make_pair(INF, -1);
	int cx = pos + size_;
	while (cx >= 2) {
		cx >>= 1;
		refresh(cx);
	}
}
 
// -------------------- Segment Tree End ----------------
 
int main() {
	//FILE *in = freopen("in1.txt", "r", stdin);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%s", &cc); string V = "";
		for (int j = 0; j < 1000000; j++) {
			if (cc[j] == 0) break;
			V += cc[j]; cc[j] = 0;
		}
		P[i] = ConvertFromString(V);
	}
	for (int i = N; i >= 1; i--) P[i] = (P[i] - P[i - 1]);
	
	init(N + 1);
	
	int cnts = 0;
	while (cnts < N) {
		pair<BigInteger, int> c = query(1, N + 1);
		int pos = c.second;
		cnts++; A[pos] = cnts;
		lose(pos + 1, N + 1, P[pos]);
		annihilation(pos);
	}
 
	for (int i = 1; i <= N; i++) { if (i >= 2) printf(" "); printf("%d", A[i]); } cout << endl;
	//cout << "count = " << cnt << endl;
	return 0;
}

Compilation message (stderr)

permutation.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
permutation.cpp: In function 'BigInteger ConvertFromString(std::__cxx11::string)':
permutation.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) {
                  ~~^~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:165:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[100009]' [-Wformat=]
   scanf("%s", &cc); string V = "";
               ~~~^
permutation.cpp:165: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 / 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