oj.uz

Submission #389523

# Submission time Handle Problem Language Result Execution time Memory
389523 2021-04-14T07:01:34 Z balbit Permutation Recovery (info1cup17_permutation) C++14
100 / 100
 3634 ms 401448 KB 
#include <bits/stdc++.h>
#undef BALBIT
#pragma GCC optimize("Ofast", "unroll-loops")
//#ifndef BALBIT
//#include "grader.h"
//#endif

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBITs
#define LL __int128

const int maxn = 7e4+5;
struct big{
    vector<ll> ho;
//    static const ll bits = 62;
    static const ll cap = 1000000000000000000ll; // each digit stores [0,cap]
    void mul(int x) {
//        bug("mul in ");
        ll over = 0;
        REP(i, SZ(ho)) {
            LL tmp = ho[i] * (LL)x + over;
            over = tmp/cap;
            ho[i] = tmp % cap;
        }
        if (over) {
            ho.pb(over);
        }
        while (SZ(ho) && ho.back() == 0) ho.pop_back();
//        bug("mul out");
    }
    void add(int x) {
        ll over = x;
        REP(i, SZ(ho)) {
            ll tmp = ho[i] + over;
            over = tmp / cap;
            ho[i] = tmp % cap;
            if (over == 0) break;
        }
        if (over) {
            ho.pb(over);
        }
        while (SZ(ho) && ho.back() == 0) ho.pop_back();
    }
    void add(big &x) {
        while (SZ(ho) < SZ(x.ho)) ho.pb(0);
//        while (SZ(ho) > SZ(x.ho)) x.ho.pb(0);
        ll over = 0;
        REP(i, SZ(ho)) {
            ll tmp = ho[i] + (i<SZ(x.ho)?x.ho[i]:0) + over;
            over = tmp / cap;
            ho[i] = tmp % cap;
            if (over == 0 && i+1>=SZ(x.ho)) break;
        }
        if (over) {
            ho.pb(over);
        }
        while (SZ(ho) && ho.back() == 0) ho.pop_back();
    }
    void sub(big &x) {
        while (SZ(ho) < SZ(x.ho)) ho.pb(0);
//        while (SZ(ho) > SZ(x.ho)) x.ho.pb(0);
        ll over = 0;
        REP(i, SZ(ho)) {
            ll tmp = ho[i] - (i < SZ(x.ho)?x.ho[i]:0) - over;
            over = 0;
            while (tmp < 0) {
                tmp += cap;
                over++;
            }
            ho[i] = tmp;
            if (over == 0 && i+1>=SZ(x.ho)) break;
        }
        if (over) {
            bug("negative number oof");
//            while (1);
        }
        while (SZ(ho) && ho.back() == 0) ho.pop_back();
    }
    bool operator == (big &x) {
        if (SZ(ho) != SZ(x.ho)) return 0;
        return x.ho == ho;
    }
    bool operator < (big &x) {
        if (SZ(x.ho) > SZ(ho)) {
            return 1;
        }
        if (SZ(ho) > SZ(x.ho)) {
            return 0;
        }
        for (int i = SZ(ho)-1; i>=0; --i) {
            if (ho[i] != x.ho[i]) {
                if (ho[i] < x.ho[i]) return 1;
                if (ho[i] > x.ho[i]) return 0;
            }
        }
        return 0;
    }
    int operator ^ (big &x) {
        if (SZ(x.ho) > SZ(ho)) {
            return 1;
        }
        if (SZ(ho) > SZ(x.ho)) {
            return -1;
        }
        for (int i = SZ(ho)-1; i>=0; --i) {
            if (ho[i] != x.ho[i]) {
                if (ho[i] < x.ho[i]) return 1;
                if (ho[i] > x.ho[i]) return -1;
            }
        }
        return 0;
    }
    big(string s) {
        ll nw = 0;
        ll p10 = 1;
        for (int i = SZ(s)-1; i>=0; --i) {
            nw += p10 * (s[i]-'0');
            p10 *= 10;
            if (p10 == cap) {
                p10 = 1;
                ho.pb(nw);
                nw = 0;
            }
        }
        if (nw) {
            ho.pb(nw);
        }
    }
    big(){}
};

pair<big, int> s [maxn*4];
big tg[maxn*4];
//bool neg[maxn*4];
int ans[maxn];
int n;

bool Ra(pair<big, int> &a, pair<big, int> &b) { // is a better than b?
    if (a.s == -1) return 0;
    if (b.s == -1) return 1;
    int y = a.f^b.f;
    return y==0? a.s > b.s : y==1;
}

void push(int o, int l, int r) {
    if (s[o].s == -1) return;
    if (tg[o].ho.empty()) return;
    s[o].f.sub(tg[o]);
    if (l!=r) {
        tg[o*2].add(tg[o]);
        tg[o*2+1].add(tg[o]);
    }
    tg[o].ho.clear();
}

big in[maxn], a[maxn], org[maxn];

void build(int o=1, int l=0, int r=n-1) {
    if (l == r) {
        s[o] = {org[l], l};
        return;
    }
    int mid = (l+r)/2;
    build(o*2,l,mid);
    build(o*2+1,mid+1,r);
    if (Ra(s[o*2], s[o*2+1])) {
        s[o] = s[o*2];
    }else{
        s[o] = s[o*2+1];
    }
}

void MO(int L, int R, big &v, bool sub, int o=1, int l=0, int r = n-1) {
    if (s[o].s == -1) return;
    push(o,l,r);
    if (l >= L && r <= R) {
        if (v.ho.empty()) return;
        s[o].f.sub(v);
        if (l!=r) {
            tg[o*2].add(v);
            tg[o*2+1].add(v);
        }
        return;
    }
    if (l > R || r < L) return;
    int mid = (l+r)/2;
    MO(L,R,v,sub,o*2,l,mid);
    MO(L,R,v,sub,o*2+1,mid+1,r);
    if (Ra(s[o*2], s[o*2+1])) {
        s[o] = s[o*2];
    }else{
        s[o] = s[o*2+1];
    }
}
big INF;
void MO2(int p, int o=1, int l=0, int r = n-1) {
    push(o,l,r);
    if (l > p || r < p) return;
    if (l == r) {
        s[o] = {INF, -1};
        return;
    }
    int mid = (l+r)/2;
    MO2(p,o*2,l,mid);
    MO2(p,o*2+1,mid+1,r);
    if (Ra(s[o*2], s[o*2+1])) {
        s[o] = s[o*2];
    }else{
        s[o] = s[o*2+1];
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
//    freopen("out.txt", "r", stdin);
//    freopen("in.txt", "r", stdin);
//    clock_t ts =clock();
    {
        char c = ' ';
        while (!(c>='0' && c<='9')) c = getchar();
        while (c>='0' && c<='9') {
            n = (n*10) + (c-'0');
            c = getchar();
        }
    }
    big ps("1");
    string bigstring;
    REP(i, 0) bigstring.pb('9');
    INF = big(bigstring);
    REP(i,n) {
        string s;
        char c = ' ';
        while (!(c>='0' && c<='9')) c = getchar();
        while (c>='0' && c<='9') {
            s.pb(c); c=getchar();
        }
        in[i] = a[i] = big(s);
        if (i) a[i].sub(in[i-1]);
        org[i] = ps;
        org[i].sub(a[i]);
        bug(org[i].ho.size()==0?0:org[i].ho[0]);
        bug(a[i].ho.size()==0?0:a[i].ho[0]);
        ps.add(a[i]);
//        if (i % 10 == 0) cout<<i<<endl<<flush;
    }
//    cout<<((clock() - ts) / (double)CLOCKS_PER_SEC)<<endl;
//    return 0;
//    cout<<org[n-1].ho[0]<<endl;
//    return 0;
    build();
//    bug(s[1].s);
    for (int i = n; i>=1; i--) {
        pair<big, int> &hi = s[1];
        int v = hi.s;
//        bug(v+1, a[v].ho[0]);
        ans[v]=i;
        MO(v+1, n-1, a[v],1);

        MO2(v);
    }

    REP(i,n) cout<<ans[i]<<' ';
    cout<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct
5 Correct 488 ms 40668 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct
5 Correct 488 ms 40668 KB Output is correct
6 Correct 967 ms 64112 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct
5 Correct 488 ms 40668 KB Output is correct
6 Correct 967 ms 64112 KB Output is correct
7 Correct 1061 ms 80976 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct
5 Correct 488 ms 40668 KB Output is correct
6 Correct 967 ms 64112 KB Output is correct
7 Correct 1061 ms 80976 KB Output is correct
8 Correct 1826 ms 256412 KB Output is correct
9 Correct 2761 ms 290432 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20556 KB Output is correct
2 Correct 14 ms 20556 KB Output is correct
3 Correct 16 ms 20828 KB Output is correct
4 Correct 17 ms 20732 KB Output is correct
5 Correct 488 ms 40668 KB Output is correct
6 Correct 967 ms 64112 KB Output is correct
7 Correct 1061 ms 80976 KB Output is correct
8 Correct 1826 ms 256412 KB Output is correct
9 Correct 2761 ms 290432 KB Output is correct
10 Correct 3634 ms 401448 KB Output is correct