Submission #390108

#	Time	Username	Problem	Language	Result	Execution time	Memory
390108		rk42745417	Permutation Recovery (info1cup17_permutation)	C++17	25 / 100	203 ms	313428 KiB

Main

/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1e7;
mt19937 rnd(time(0));
struct Treap {
	struct node {
		int l, r, sz, pri;
		ll val, sum;
		node(): l(0), r(0), sz(0), val(0), sum(0), pri(0) { }
		node(ll x): l(0), r(0), sz(1), val(x), sum(x), pri(rnd()) { }
	} arr[N];
	int t;
	inline int new_node(ll v) {
		arr[++t] = node(v);
		return t;
	}
	inline void pull(int p) {
		arr[p].sz = sz(arr[p].l) + 1 + sz(arr[p].r);
		arr[p].sum = arr[arr[p].l].sum + arr[p].val + arr[arr[p].r].sum;
	}
	inline int sz(int p) { return arr[p].sz; }
	void split(int &a, int &b, int id, ll v) {
		if(!id)
			return a = b = 0, void();
		if(arr[arr[id].l].sum + arr[id].val <= v) {
			a = id;
			split(arr[a].r, b, arr[id].r, v - (arr[arr[id].l].sum + arr[id].val));
			pull(a);
		}
		else {
			b = id;
			split(a, arr[b].l, arr[id].l, v);
			pull(b);
		}
	}
	int merge(int a, int b) {
		if(!a || !b)
			return a ? a : b;
		if(arr[a].pri > arr[b].pri) {
			arr[a].r = merge(arr[a].r, b);
			pull(a);
			return a;
		}
		else {
			arr[b].l = merge(a, arr[b].l);
			pull(b);
			return b;
		}
	}
	void travesal(int id, vector<int> &ans, int g) {
		if(!id)
			return;
		travesal(arr[id].l, ans, g);
		g += sz(arr[id].l) + 1;
		//cout << "here " <<
		ans[id] = g;
		travesal(arr[id].r, ans, g);
	}
} treap;

signed main() { EmiliaMyWife
	int n, rt = 0;
	cin >> n;
	vector<ll> arr(n);
	for(auto &a : arr)
		cin >> a;
	vector<int> ans(n + 1);
	for(int i = 0; i < n; i++) {
		int a, b;
		ll x = arr[i];
		if(i)
			x -= arr[i - 1];
		treap.split(a, b, rt, x - 1);
		rt = treap.merge(a, treap.new_node(x));
		rt = treap.merge(rt, b);
	}
	treap.travesal(rt, ans, 0);
	for(int i = 1; i <= n; i++)
		cout << ans[i] << " \n"[i == n];
}

Compilation message (stderr)

permutation.cpp: In constructor 'Treap::node::node()':
permutation.cpp:31:11: warning: 'Treap::node::sum' will be initialized after [-Wreorder]
   31 |   ll val, sum;
      |           ^~~
permutation.cpp:30:17: warning:   'int Treap::node::pri' [-Wreorder]
   30 |   int l, r, sz, pri;
      |                 ^~~
permutation.cpp:32:3: warning:   when initialized here [-Wreorder]
   32 |   node(): l(0), r(0), sz(0), val(0), sum(0), pri(0) { }
      |   ^~~~
permutation.cpp: In constructor 'Treap::node::node(ll)':
permutation.cpp:31:11: warning: 'Treap::node::sum' will be initialized after [-Wreorder]
   31 |   ll val, sum;
      |           ^~~
permutation.cpp:30:17: warning:   'int Treap::node::pri' [-Wreorder]
   30 |   int l, r, sz, pri;
      |                 ^~~
permutation.cpp:33:3: warning:   when initialized here [-Wreorder]
   33 |   node(ll x): l(0), r(0), sz(1), val(x), sum(x), pri(rnd()) { }
      |   ^~~~

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