oj.uz

Submission #389982

# Submission time Handle Problem Language Result Execution time Memory
389982 2021-04-15T03:16:12 Z syl123456 Permutation Recovery (info1cup17_permutation) C++17
100 / 100
 2142 ms 101660 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pp;
const ll k = 1e18;
struct big_num {
    vector<ll> v;
    big_num(string s) {
        while (!s.empty()) {
            ll tmp = 0, base = 1;
            while (base < k && !s.empty())
                tmp += base * (s.back() - '0'), s.pop_back(), base *= 10;
            v.push_back(tmp);
        }
    }
};
int cmp(big_num x, big_num y) {
    if (x.v.size() != y.v.size()) return x.v.size() > y.v.size() ? 1 : -1;
    for (int i = x.v.size() - 1; ~i; --i)
        if (x.v[i] != y.v[i]) return x.v[i] > y.v[i] ? 1 : -1;
    return 0;
}
big_num add(big_num x, big_num y) {
    bool c = false;
    for (int i = 0; i < min(x.v.size(), y.v.size()); ++i) {
        x.v[i] += y.v[i] + c;
        if (x.v[i] < k) c = false;
        else x.v[i] -= k, c = true;
        y.v[i] = x.v[i];
    }
    if (x.v.size() < y.v.size()) {
        for (int i = x.v.size(); i < y.v.size() && c; ++i) {
            ++y.v[i];
            if (y.v[i] == k) y.v[i] = 0;
            else c = false;
        }
        if (c) y.v.push_back(1);
        return y;
    }
    for (int i = y.v.size(); i < x.v.size() && c; ++i) {
        ++x.v[i];
        if (x.v[i] == k) x.v[i] = 0;
        else c = false;
    }
    if (c) x.v.push_back(1);
    return x;
}
big_num sub(big_num x, big_num y) {
    bool c = false;
    for (int i = 0; i < y.v.size(); ++i) {
        y.v[i] += c;
        if (x.v[i] >= y.v[i]) x.v[i] -= y.v[i], c = false;
        else x.v[i] -= y.v[i] - k, c = true;
    }
    for (int i = y.v.size(); i < x.v.size() && c; ++i) {
        --x.v[i];
        if (x.v[i] == -1) x.v[i] = k - 1;
        else c = false;
    }
    while (x.v.size() > 1 && x.v.back() == 0) x.v.pop_back();
    return x;
}
vector<big_num> s;
vector<int> ans;
int it;
struct splaytree {
    vector<int> v, pa;
    vector<big_num> sz;
    vector<array<int, 2>> ch;
    int rt;
    splaytree() : v(1, 0), pa(1, -1), sz(1, s[0]), ch(1), rt(0) {
        ch[0][0] = ch[0][1] = -1;
    }
    void rotate(int i) {
        int p = pa[i], gp = pa[p];
        int x = ch[p][1] == i;
        int c = ch[i][!x];
        sz[p] = sub(sz[p], sz[i]);
        sz[i] = add(sz[i], sz[p]);
        if (~c) sz[p] = add(sz[p], sz[c]), pa[c] = p;
        ch[p][x] = c, ch[i][!x] = p;
        pa[p] = i, pa[i] = gp;
        if (~gp) ch[gp][ch[gp][1] == p] = i;
    }
    void splay(int i) {
        while (~pa[i]) {
            if (pa[pa[i]] == -1) rotate(i);
            else if (ch[pa[pa[i]]][0] == pa[i] ^ ch[pa[i]][0] == i)
                rotate(i), rotate(i);
            else rotate(pa[i]), rotate(i);
        }
        rt = i;
    }
    void insert(int i) {
        big_num rem = sub(s[i], big_num("1"));
        int x = rt;
        while (~x) {
            big_num pre = ~ch[x][1] ? sub(sz[x],sz[ch[x][1]]) : sz[x];
            int tmp = cmp(rem, pre);
            if (tmp == 1) rem = sub(rem, pre), x = ch[x][1];
            else if (tmp == 0) break;
            else x = ch[x][0];
        }
        if (x == -1) {
            int id = v.size();
            v.push_back(i);
            pa.push_back(-1);
            ch.emplace_back();
            ch[id][0] = -1, ch[id][1] = rt;
            sz.push_back(add(s[i], sz[rt])), pa[rt] = id;
            rt = id;
            return;
        }
        splay(x);
        int id = v.size();
        v.push_back(i);
        pa.push_back(x);
        sz[x] = add(sz[x], s[i]);
        ch.emplace_back();
        ch[id][0] = -1, ch[id][1] = ch[x][1];
        ch[x][1] = id;
        if (~ch[id][1]) sz.push_back(add(s[i], sz[ch[id][1]])), pa[ch[id][1]] = id;
        else sz.push_back(s[i]);
    }
    void get_ans(int i = -1) {
        if (i == -1) i = rt;
        if (~ch[i][0]) get_ans(ch[i][0]);
        ans[v[i]] = ++it;
        if (~ch[i][1]) get_ans(ch[i][1]);
    }
};
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string x;
        cin >> x;
        s.emplace_back(x);
    }
    for (int i = n - 1; i; --i) s[i] = sub(s[i], s[i - 1]);
    splaytree rt = splaytree();
    for (int i = 1; i < n; ++i) rt.insert(i);
    ans.resize(n);
    rt.get_ans();
    for (int i : ans) cout << i << ' ';
}

Compilation message

permutation.cpp: In function 'big_num add(big_num, big_num)':
permutation.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   38 |     for (int i = 0; i < min(x.v.size(), y.v.size()); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
permutation.cpp:45:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = x.v.size(); i < y.v.size() && c; ++i) {
      |                                  ~~^~~~~~~~~~~~
permutation.cpp:53:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = y.v.size(); i < x.v.size() && c; ++i) {
      |                              ~~^~~~~~~~~~~~
permutation.cpp: In function 'big_num sub(big_num, big_num)':
permutation.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < y.v.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
permutation.cpp:68:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = y.v.size(); i < x.v.size() && c; ++i) {
      |                              ~~^~~~~~~~~~~~
permutation.cpp: In member function 'void splaytree::splay(int)':
permutation.cpp:101:39: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
  101 |             else if (ch[pa[pa[i]]][0] == pa[i] ^ ch[pa[i]][0] == i)

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 598 ms 8496 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 598 ms 8496 KB Output is correct
6 Correct 1207 ms 17364 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 598 ms 8496 KB Output is correct
6 Correct 1207 ms 17364 KB Output is correct
7 Correct 1114 ms 36472 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 598 ms 8496 KB Output is correct
6 Correct 1207 ms 17364 KB Output is correct
7 Correct 1114 ms 36472 KB Output is correct
8 Correct 1053 ms 101660 KB Output is correct
9 Correct 1739 ms 64604 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 598 ms 8496 KB Output is correct
6 Correct 1207 ms 17364 KB Output is correct
7 Correct 1114 ms 36472 KB Output is correct
8 Correct 1053 ms 101660 KB Output is correct
9 Correct 1739 ms 64604 KB Output is correct
10 Correct 2142 ms 97216 KB Output is correct