oj.uz

Submission #389551

# Submission time Handle Problem Language Result Execution time Memory
389551 2021-04-14T07:19:12 Z Kevin_Zhang_TW Permutation Recovery (info1cup17_permutation) C++17
78 / 100
 4000 ms 116132 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
 
unsigned mrand() {
	static unsigned x = 12323421;
	return (++x) *= 0xdefaced;
}
 
const ll MAX_N = 100000, BD = 1e13, WID = 13;
 
struct mint {
	vector<ll> val;
	mint(string s = "0") {
		ll len = 0, v = 0, sc = 1;
		reverse(AI(s));
		for (int i = 0;i < s.size();++i) {
			v += sc * (s[i] - '0');
			if (++len == WID) {
				val.pb(v);
				v = len = 0, sc = 1;
			}
			if (len) sc *= 10;
		}
		val.pb(v);
	}
	mint(vector<ll> v) : val(v) { upd(); }
	mint(ll v) { val = {v}; upd(); }
	void shrink() { while (val.size() > 1 && val.back() == 0) val.pop_back(); }
	void upd() {
		for (int i = 0;i < val.size();++i) {
			if (val[i] >= BD) {
				if (i+1 == val.size()) val.pb(0);
				val[i+1] += val[i] / BD;
				val[i] %= BD;
			}
			while (val[i] < 0) {
				--val[i+1];
				val[i] += BD;
			}
		}
		shrink();
	}
	bool operator < (mint b) {
		auto &A = val, &B = b.val;
		if (A.size() != B.size()) 
			return A.size() < B.size();
		for (int i = A.size() - 1;i >= 0;--i)
			if (A[i] != B[i])
				return A[i] < B[i];
		return false;
	}
	bool operator > (mint b) {
		return b < *this;
	}
	bool operator <= (mint b) { 
		return !(b < *this);
	}
	bool operator == (mint b) {
		return !(*this < b) && (!(b < *this));
	}
	friend ostream& operator << (ostream& out, mint a) {
		auto &val = a.val;
		for (int i = (int)val.size()-1;i >= 0;--i) 
			out << setw(9) << setfill('0') << val[i];
		return out;
	}
};
mint operator - (mint a, mint b) {
	auto A = a.val, B = b.val;
	int sz = max(A.size(), B.size());
	A.resize(sz), B.resize(sz);
	for (int i = 0;i < A.size();++i)
		A[i] -= B[i];
	return mint(A);
}
mint& operator -= (mint &a, mint b) { return a = a - b; }
mint operator + (mint a, mint b) {
	auto A = a.val, B = b.val;
	int sz = max(A.size(), B.size());
	A.resize(sz), B.resize(sz);
	for (int i = 0;i < A.size();++i)
		A[i] += B[i];
	return mint(A);
}
mint& operator += (mint &a, mint b) { return a = a + b; }
 
 
//#define mint ll
 
struct node {
	mint sum, val;
	int l, r;
	unsigned pri;
	int ind;
}room[MAX_N];
 
int new_mem(mint val = 0, int ind = 0) {
	static int mem;
	room[++mem] = {val, val, 0, 0, mrand(), ind};
	return mem;
}
 
#define P(i) room[i].pri
#define L(i) room[i].l
#define R(i) room[i].r
#define S(i) room[i].sum
#define V(i) room[i].val
#define ID(i) room[i].ind
 
void upd(int ind) {
	S(ind) = S(L(ind)) + S(R(ind)) + V(ind);
}
 
int merge(int a, int b) {
	if (a == 0) return b;
	if (b == 0) return a;
	if (P(a) < P(b)) {
		R(a) = merge(R(a), b);
		upd(a);
		return a;
	}
	else {
		L(b) = merge(a, L(b));
		upd(b);
		return b;
	}
}
 
void split(int root, mint sum, int &a, int &b) {
	if (root == 0) {
		a = b = 0;
		return;
	}
	if (S(L(root)) + V(root) <= sum) {
		sum -= S(L(root)) + V(root);
		a = root;
		split(R(root), sum, R(a), b);
		upd(a);
	}
	else {
		b = root;
		split(L(root), sum, a, L(b));
		upd(b);
	}
}
vector<int> order;
void dfs(int now) {
	if (now == 0) return;
	dfs(L(now));
	order.pb(ID(now));
	dfs(R(now));
}
 
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
 
	int n;
	cin >> n;
 
	vector<pair<int, mint>> per;
 
	vector<mint> val(n);
 
	for (mint &a : val) {
 
		//cin >> a;
 
		string v;
		cin >> v;
		a = mint(v);
	}
 
	for (int i = n-1;i > 0;--i) {
		val[i] -= val[i-1];
	}
 
	int root = 0;
 
	for (int i = 0;i < n;++i) {
 
		mint v = val[i] - 1;
 
		int a, b;
 
		split(root, v, a, b);
 
		int now = new_mem(val[i]);
 
		ID(now) = i;

		root = merge(a, merge(now, b));
 
	}
 
	dfs(root);
 
	vector<int> ans(n);
	for (int i = 0;i < n;++i) {
		int id = order[i];
		ans[id] = i+1;
	}
 
	for (int i = 0;i < n;++i)
		cout << ans[i] << " \n"[i+1==n];
}

Compilation message

permutation.cpp: In constructor 'mint::mint(std::string)':
permutation.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int i = 0;i < s.size();++i) {
      |                  ~~^~~~~~~~~~
permutation.cpp: In member function 'void mint::upd()':
permutation.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for (int i = 0;i < val.size();++i) {
      |                  ~~^~~~~~~~~~~~
permutation.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if (i+1 == val.size()) val.pb(0);
      |         ~~~~^~~~~~~~~~~~~
permutation.cpp: In function 'mint operator-(mint, mint)':
permutation.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (int i = 0;i < A.size();++i)
      |                 ~~^~~~~~~~~~
permutation.cpp: In function 'mint operator+(mint, mint)':
permutation.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (int i = 0;i < A.size();++i)
      |                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct
5 Correct 1659 ms 21000 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct
5 Correct 1659 ms 21000 KB Output is correct
6 Correct 3324 ms 30108 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct
5 Correct 1659 ms 21000 KB Output is correct
6 Correct 3324 ms 30108 KB Output is correct
7 Correct 3972 ms 37724 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct
5 Correct 1659 ms 21000 KB Output is correct
6 Correct 3324 ms 30108 KB Output is correct
7 Correct 3972 ms 37724 KB Output is correct
8 Execution timed out 4072 ms 116132 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12748 KB Output is correct
2 Correct 22 ms 12864 KB Output is correct
3 Correct 32 ms 13068 KB Output is correct
4 Correct 26 ms 12876 KB Output is correct
5 Correct 1659 ms 21000 KB Output is correct
6 Correct 3324 ms 30108 KB Output is correct
7 Correct 3972 ms 37724 KB Output is correct
8 Execution timed out 4072 ms 116132 KB Time limit exceeded
9 Halted 0 ms 0 KB -