Submission #199329

#	Time	Username	Problem	Language	Result	Execution time	Memory
199329		Pankin	Permutation Recovery (info1cup17_permutation)	C++14	10 / 100	47 ms	24568 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int osn = 1000000000;

class bigint {

    bigint mult(bigint a, bigint b) {
        vector<int> res(a.digits.size() + b.digits.size() + 5, 0);

        for (int j = 0; j < b.digits.size(); j++) {
            for (int i = 0; i < a.digits.size(); i++) {
                res[i + j] += b.digits[j] * a.digits[i];
            }
            for (int i = 0; i < res.size(); i++) {
                if (i == res.size() - 1) {
                    if (res[i] / osn > 0)
                        res.pb(0);
                    else
                        break;
                }
                res[i + 1] += res[i] / osn;
                res[i] %= osn;
            }
        }
        while(res.size() != 1 && res.back() == 0)
            res.pop_back();

        return bigint(res, a.neg ^ b.neg);
    }
    bigint sum(bigint a, bigint b) {
        if (a.neg == b.neg) {
            vector<int> res(max(a.digits.size(), b.digits.size()) + 5);
            while(a.digits.size() < b.digits.size()) {
                a.digits.pb(0);
            }
            while(b.digits.size() < a.digits.size()) {
                b.digits.pb(0);
            }

            for (int i = 0; i < a.digits.size(); i++) {
                res[i] = a.digits[i] + b.digits[i];
            }
            for (int i = 0; i < res.size(); i++) {
                if (i == res.size() - 1) {
                    if (res[i] / osn > 0)
                        res.pb(0);
                    else
                        break;
                }
                res[i + 1] += res[i] / osn;
                res[i] %= osn;
            }
            while(res.size() != 1 && res.back() == 0)
                res.pop_back();
            return bigint(res, a.neg);
        }
        if (a.neg == 0)
            swap(a, b);
        a.neg = 0;
        if (a < b)
            return subtract(b, a);
        bigint res = subtract(a, b);
        return bigint(res.digits, 1);
    }

    bigint subtract(bigint a, bigint b) {
        if (a.neg == 0 && b.neg == 0) {
            if (a < b) {
                return bigint(subtract(b, a).digits, 1);
            }
            vector<int> res(max(a.digits.size(), b.digits.size()) + 5);
            while(a.digits.size() < b.digits.size()) {
                a.digits.pb(0);
            }
            while(b.digits.size() < a.digits.size()) {
                b.digits.pb(0);
            }

            for (int i = 0; i < a.digits.size(); i++) {
                res[i] = a.digits[i] - b.digits[i];
            }
            for (int i = 0; i < res.size(); i++) {
                while(res[i] < 0) {
                    res[i] += osn;
                    res[i + 1]--;
                }
            }
            while(res.size() != 1 && res.back() == 0)
                res.pop_back();
            return bigint(res);
        }
        return sum(a, bigint(b.digits, b.neg ^ 1));
    }

public:
    vector<int> digits;
    int neg;

    bigint(int x, int ng = 0) {
        neg = ng;
        if (x < 0) {
            neg = 1;
            x = -x;
        }
        if (x == 0) {
            digits.pb(0);
            return;
        }
        while(x > 0) {
            digits.pb(x % osn);
            x /= osn;
        }
    }
    bigint(vector<int> d, int neg = 0) {
        digits = d;
        this->neg = neg;
    }
    bigint(){};
    void operator += (const bigint other) {
        bigint res = sum(bigint(this->digits, this->neg), other).digits;
        this->digits = res.digits;
        this->neg = res.neg;
    }
    bigint operator + (const bigint other) {
        return sum(bigint(this->digits), other);
    }

    void operator *= (const bigint other) {
        bigint res = mult(bigint(this->digits, this->neg), other).digits;
        this->digits = res.digits;
        this->neg = res.neg;
    }
    bigint operator * (const bigint other) {
        return mult(bigint(this->digits), other);
    }
    void operator -= (const bigint other) {
        bigint res = subtract(bigint(this->digits, this->neg), other).digits;
        this->digits = res.digits;
        this->neg = res.neg;
    }
    bigint operator - (const bigint other) {
        return subtract(bigint(this->digits, this->neg), other);
    }

    bool operator != (const bigint other) const {
        return digits != other.digits || (neg != other.neg && digits.back() != 0);
    }
    bool operator < (const bigint other) const {
        if (neg != other.neg) {
            return neg > other.neg;
        }
        if (digits.size() != other.digits.size())
            return digits.size() < other.digits.size();
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i])
                return digits[i] < other.digits[i];
        }
        return false;
    }
};

const int N = 70000 + 50;

bigint t[4 * N], pt[4 * N], q[N], ans[N], need[N];
bool del[N];
int p[N], n;
bigint cursum = bigint(1);

inline void push(int v, int tl, int tr) {
    t[v] -= pt[v];
    if (tl != tr) {
        pt[v * 2] += pt[v];
        pt[v * 2 + 1] += pt[v];
    }
    pt[v] = bigint(0);
}

void inc(int v, int tl, int tr, int l, int r, bigint x) {
    push(v, tl, tr);
    if (tl > r || tr < l)
        return;
    if (tl >= l && tr <= r) {
        pt[v] += x;
        push(v, tl, tr);
        return;
    }

    int tm = (tl + tr) / 2;
    inc(v * 2, tl, tm, l, r, x);
    inc(v * 2 + 1, tm + 1, tr, l, r, x);

    t[v] = bigint(-1);
    if (t[v * 2].neg == 0 && (t[v * 2 + 1].neg == 1 || t[v * 2] < t[v * 2 + 1]))
        t[v] = t[v * 2];
    else
        t[v] = t[v * 2 + 1];
}

int getPos(int v, int tl, int tr) {
    push(v, tl, tr);
    if (tl == tr) {
        t[v] = bigint(-1);
        return tl;
    }

    int tm = (tl + tr) / 2, ans;
    push(v * 2, tl, tm);
    push(v * 2 + 1, tm + 1, tr);

    if (!(t[v * 2 + 1] != bigint(0)))
        ans = getPos(v * 2 + 1, tm + 1, tr);
    else
        ans = getPos(v * 2, tl, tm);

    t[v] = bigint(-1);
    if (t[v * 2].neg == 0 && (t[v * 2 + 1].neg == 1 || t[v * 2] < t[v * 2 + 1]))
        t[v] = t[v * 2];
    else
        t[v] = t[v * 2 + 1];

    return ans;
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = need[tl];
        return;
    }

    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);

    if (t[v * 2] < t[v * 2 + 1])
        t[v] = t[v * 2];
    else
        t[v] = t[v * 2 + 1];
}

signed main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        int cur = 0;
        vector<int> d;
        for (int j = 0; j < s.size(); j++) {
            if (j % 9 == 0) {
                d.pb(cur);
                cur = 0;
            }
            cur = cur * 10 + s[j] - '0';
        }
        d.pb(cur);
        reverse(d.begin(), d.end());
        q[i] = bigint(d);
    }
    ans[0] = q[0];
    for (int i = 1; i < n; i++)
        ans[i] = q[i] - q[i - 1];

    for (int i = 0; i < n; i++) {
        need[i] = cursum - ans[i];
        cursum += ans[i];
    }
    build(1, 0, n - 1);

    for (int i = n; i >= 1; i--) {
        int pos = getPos(1, 0, n - 1);

        p[pos] = i;

        inc(1, 0, n - 1, pos, n - 1, ans[pos]);
    }

    for (int i = 0; i < n; i++)
        cout << p[i] << " ";



    return 0;
}

Compilation message (stderr)

permutation.cpp: In member function 'bigint bigint::mult(bigint, bigint)':
permutation.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < b.digits.size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~
permutation.cpp:49:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < a.digits.size(); i++) {
                             ~~^~~~~~~~~~~~~~~~~
permutation.cpp:52:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < res.size(); i++) {
                             ~~^~~~~~~~~~~~
permutation.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (i == res.size() - 1) {
                     ~~^~~~~~~~~~~~~~~~~
permutation.cpp: In member function 'bigint bigint::sum(bigint, bigint)':
permutation.cpp:78:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < a.digits.size(); i++) {
                             ~~^~~~~~~~~~~~~~~~~
permutation.cpp:81:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < res.size(); i++) {
                             ~~^~~~~~~~~~~~
permutation.cpp:82:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (i == res.size() - 1) {
                     ~~^~~~~~~~~~~~~~~~~
permutation.cpp: In member function 'bigint bigint::subtract(bigint, bigint)':
permutation.cpp:117:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < a.digits.size(); i++) {
                             ~~^~~~~~~~~~~~~~~~~
permutation.cpp:120:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < res.size(); i++) {
                             ~~^~~~~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:287:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.size(); j++) {
                         ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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