oj.uz

Submission #389650

# Submission time Handle Problem Language Result Execution time Memory
389650 2021-04-14T10:39:26 Z 2qbingxuan Permutation Recovery (info1cup17_permutation) C++14
94 / 100
 4000 ms 154044 KB 
#pragma GCC optimize("Ofast")
#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 = 1e18, WID = 18, MAX_D = 65;
 
 
struct BigInteger : vector<int> {
    static constexpr int base = 1000000000;
    static constexpr int width = 9;
    BigInteger() {}
    BigInteger(int x) : vector<int>{x} {}
    friend istream & operator>>(istream &I, BigInteger &n) {
        string s;
        I >> s;
        n.reserve(s.size() / 9);
        reverse(s.begin(), s.end());
        int cur = 0, cnt = 0, p = 1;
        for (char c: s) {
            cur = cur + (c - '0') * p;
            if (++cnt == width) {
                n.emplace_back(cur);
                cur = 0;
                cnt = 0;
                p = 1;
            } else {
                p *= 10;
            }
        }
        if (cnt)
            n.emplace_back(cur);
        return I;
    }
    BigInteger& operator+=(const BigInteger &rhs) {
        if (size() < rhs.size()) resize(rhs.size());
        int carry = 0;
        for (size_t i = 0; i < size(); i++) {
            at(i) += (i < rhs.size() ? rhs[i] : 0) + carry;
            carry = at(i) / base;
            at(i) %= base;
        }
        if (carry)
            push_back(carry);
        return *this;
    }
    BigInteger& operator-=(const BigInteger &rhs) {
        int carry = 0;
        for (size_t i = 0; i < size(); i++) {
            at(i) -= (i < rhs.size() ? rhs[i] : 0) + carry;
            if (at(i) < 0) {
                at(i) += base;
                carry = 1;
            } else {
                carry = 0;
            }
        }
        while (!empty() && back() == 0) pop_back();
        return *this;
    }
    friend bool operator<(const BigInteger &x, const BigInteger &y) {
        if (x.size() != y.size()) return x.size() < y.size();
        if (x.empty()) return false;
        for (int i = x.size()-1; i >= 0; i--)
            if (x[i] != y[i])
                return x[i] < y[i];
        return false;
    }
    friend bool operator>=(const BigInteger &x, const BigInteger &y) { return !(x < y); }
    friend bool operator>(const BigInteger &x, const BigInteger &y) { return y < x; }
    friend bool operator<=(const BigInteger &x, const BigInteger &y) { return !(y < x); }
    friend BigInteger operator+(BigInteger a, const BigInteger &b) {
        return a += b;
    }
    friend BigInteger operator-(BigInteger a, const BigInteger &b) {
        return a -= b;
    }
    friend ostream & operator<<(ostream &O, BigInteger n) {
        return O << n[0];
    }
};

using mint = BigInteger;
 
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<mint> val(n);
 
	{
            for (int i = 0; i < n; i++) cin >> val[i];
            /*
		vector<string> inp(n);
		for (auto &i : inp) cin >> i;
 
		for (int i = 0;i < n;++i)
			val[i] = mint(inp[i]);
                        */
	}
 
//	for (mint &a : val) {
// 
//		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];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct
5 Correct 638 ms 16412 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct
5 Correct 638 ms 16412 KB Output is correct
6 Correct 1351 ms 27188 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct
5 Correct 638 ms 16412 KB Output is correct
6 Correct 1351 ms 27188 KB Output is correct
7 Correct 1620 ms 34992 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct
5 Correct 638 ms 16412 KB Output is correct
6 Correct 1351 ms 27188 KB Output is correct
7 Correct 1620 ms 34992 KB Output is correct
8 Correct 3236 ms 141700 KB Output is correct
9 Correct 3897 ms 115924 KB Output is correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 6 ms 6604 KB Output is correct
3 Correct 9 ms 6604 KB Output is correct
4 Correct 8 ms 6680 KB Output is correct
5 Correct 638 ms 16412 KB Output is correct
6 Correct 1351 ms 27188 KB Output is correct
7 Correct 1620 ms 34992 KB Output is correct
8 Correct 3236 ms 141700 KB Output is correct
9 Correct 3897 ms 115924 KB Output is correct
10 Execution timed out 4078 ms 154044 KB Time limit exceeded