oj.uz

Submission #389384

# Submission time Handle Problem Language Result Execution time Memory
389384 2021-04-14T03:50:57 Z balbit Permutation Recovery (info1cup17_permutation) C++14
78 / 100
 4000 ms 77696 KB 
#include <bits/stdc++.h>
#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 = (1ll<<bits)-1; // 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 >>bits;
            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 >>bits;
            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] + x.ho[i] + over;
            over = tmp >>bits;
            ho[i] = tmp & cap;
        }
        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] - x.ho[i] - over;
            over = 0;
            while (tmp < 0) {
                tmp += (1ll<<bits);
                over++;
            }
            ho[i] = tmp;
        }
        if (over) {
            bug("negative number oof");
//            while (1);
        }
        while (SZ(ho) && ho.back() == 0) ho.pop_back();
    }
    bool operator == (big x) {
        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;
    }
    big(string s) {
        for (char c : s){
            mul(10);
            add(c-'0');
        }
    }
    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;
    return a.f == b.f? a.s > b.s : a.f<b.f;
}

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) {
    push(o,l,r);
    if (l > R || r < L) return;
    if (l >= L && r <= R) {
        if (sub)
            tg[o].add(v);
        push(o,l,r);
        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);
    cin>>n;
    big ps("1");
    string bigstring;
    REP(i, 0) bigstring.pb('9');
    INF = big(bigstring);
    REP(i,n) {
        string s; cin>>s;
        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]);
    }
    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 13 ms 20556 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct
5 Correct 719 ms 39868 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct
5 Correct 719 ms 39868 KB Output is correct
6 Correct 1527 ms 60212 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct
5 Correct 719 ms 39868 KB Output is correct
6 Correct 1527 ms 60212 KB Output is correct
7 Correct 1777 ms 77696 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct
5 Correct 719 ms 39868 KB Output is correct
6 Correct 1527 ms 60212 KB Output is correct
7 Correct 1777 ms 77696 KB Output is correct
8 Execution timed out 4067 ms 45936 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20556 KB Output is correct
2 Correct 14 ms 20684 KB Output is correct
3 Correct 17 ms 20748 KB Output is correct
4 Correct 16 ms 20684 KB Output is correct
5 Correct 719 ms 39868 KB Output is correct
6 Correct 1527 ms 60212 KB Output is correct
7 Correct 1777 ms 77696 KB Output is correct
8 Execution timed out 4067 ms 45936 KB Time limit exceeded
9 Halted 0 ms 0 KB -