Submission #389535

#	Time	Username	Problem	Language	Result	Execution time	Memory
389535		abc864197532	Permutation Recovery (info1cup17_permutation)	C++17	100 / 100	3792 ms	237752 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
    for (auto a : x) cout << a << ' '; \
    cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 512, abc = 864197532, K = 18;
const long long base = pow(10, K);

struct BigInt {
    vector <lli> val;
    BigInt(string s = "0") {
        int cnt = 0;
        lli pre = 0, pww = 1;
        for (int i = s.length() - 1; ~i; --i) {
            cnt++;
            pre += pww * (s[i] - '0');
            pww *= 10;
            if (cnt == K) val.pb(pre), cnt = pre = 0, pww = 1;
        }
        if (cnt) val.pb(pre);
    }
    BigInt operator - (const BigInt &o) const {
        vector <lli> result(max(val.size(), o.val.size()));
        for (int i = 0; i < result.size(); ++i) {
            lli a = i < val.size() ? val[i] : 0;
            lli b = i < o.val.size() ? o.val[i] : 0;
            result[i] = a - b;
        }
        for (int i = 0; i < result.size(); ++i) {
            if (result[i] < 0) {
                int add = (-result[i] + base - 1) / base;
                result[i + 1] -= add;
                result[i] += add * base;
            }
        }
        while (result.size() > 1 && result.back() == 0) result.pop_back();
        BigInt ans;
        ans.val.pop_back();
        for (lli i : result) ans.val.pb(i);
        return ans;
    }
    BigInt operator + (const BigInt &o) const {
        vector <lli> result(max(val.size(), o.val.size()));
        for (int i = 0; i < result.size(); ++i) {
            lli a = i < val.size() ? val[i] : 0;
            lli b = i < o.val.size() ? o.val[i] : 0;
            result[i] = a + b;
        }
        for (int i = 0; i < result.size(); ++i) {
            if (result[i] >= base && i == result.size() - 1) result.pb(0);
            result[i + 1] += result[i] / base;
            result[i] %= base;
        }
        while (result.size() > 1 && result.back() == 0) result.pop_back();
        BigInt ans;
        ans.val.pop_back();
        for (lli i : result) ans.val.pb(i);
        return ans;
    }
    bool operator == (const BigInt &o) const {
        return val == o.val;
    }
    bool operator < (const BigInt &o) const {
        if (val.size() != o.val.size()) return val.size() < o.val.size();
        for (int i = val.size() - 1; ~i; --i) if (val[i] != o.val[i]) {
            return val[i] < o.val[i];
        }
        return false;
    }
} one = BigInt("1"), zero;

struct Seg {
    int l, r, m, cnt;
    BigInt mn, lz;
    Seg* ch[2];
    Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1), cnt(0) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m, a);
            ch[1] = new Seg(m, r, a);
            pull();
        } else {
            mn = a[l];
        }
    }
    bool INF() {
        return cnt == r - l;
    }
    void pull() {
        if (INF()) return;
        if (ch[0]->INF()) mn = ch[1]->mn;
        else if (ch[1]->INF()) mn = ch[0]->mn;
        else if (ch[0]->mn < ch[1]->mn) mn = ch[0]->mn;
        else mn = ch[1]->mn;
    }
    void give(BigInt i) {
        if (INF()) return;
        lz = lz + i;
        mn = mn - i;
    }
    void push() {
        if (INF()) return;
        if (lz == zero) return;
        ch[0]->give(lz), ch[1]->give(lz);
        lz = zero;
    }
    void modify(int a, int b, BigInt v) {
        if (a <= l && r <= b) give(v);
        else {
            push();
            if (a < m) ch[0]->modify(a, b, v);
            if (m < b) ch[1]->modify(a, b, v);
            pull();
        }
    }
    int query() {
        if (r - l == 1) {
            cnt++;
            return l;
        }
        push();
        int ans;
        if (!ch[1]->INF() && ch[1]->mn == one) ans = ch[1]->query();
        else ans = ch[0]->query();
        pull();
        cnt++;
        return ans;
    }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector <BigInt> a;
    string s;
    for (int i = 0; i < n; ++i) cin >> s, a.pb(BigInt(s));
    vector <BigInt> d(n);
    vector <int> p(n, 0);
    int now = 1;
    for (int i = 0; i < n; ++i) {
        d[i] = (i ? a[i] - a[i - 1] : a[i]);
    }
    Seg root(0, n, d);
    while (now <= n) {
        int i = root.query();
        p[i] = now++;
        root.modify(i, n, d[i]);
    }
    printv(p);
}

Compilation message (stderr)

permutation.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
permutation.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             lli a = i < val.size() ? val[i] : 0;
      |                     ~~^~~~~~~~~~~~
permutation.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             lli b = i < o.val.size() ? o.val[i] : 0;
      |                     ~~^~~~~~~~~~~~~~
permutation.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
permutation.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             lli a = i < val.size() ? val[i] : 0;
      |                     ~~^~~~~~~~~~~~
permutation.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             lli b = i < o.val.size() ? o.val[i] : 0;
      |                     ~~^~~~~~~~~~~~~~
permutation.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < result.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~
permutation.cpp:62:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if (result[i] >= base && i == result.size() - 1) result.pb(0);
      |                                      ~~^~~~~~~~~~~~~~~~~~~~
permutation.cpp: In constructor 'Seg::Seg(int, int, std::vector<BigInt>&)':
permutation.cpp:88:66: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     Seg (int _l, int _r, vector <BigInt> &a) : l(_l), r(_r), m(l + r >> 1), cnt(0) {
      |                                                                ~~^~~

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