Submission #1320253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320253		andrei_n	Permutation Recovery (info1cup17_permutation)	C++20	0 / 100	3 ms	548 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v[70005];
int p[70005];

vector<int> getBig(string s) {
    vector<int> r;
    for(auto it = s.rbegin(); it != s.rend(); ++it) {
        r.push_back(*it - '0');
    }
    return r;
}

void printBig(vector<int> x) {
    if(x.size() == 0) {
        cout<<'0';
    }
    for(auto it = x.rbegin(); it != x.rend(); ++it) {
        cout<<*it;
    }
}

vector<int> addBig(vector<int> a, vector<int> b) {
    if(a.size() < b.size()) {
        swap(a, b);
    }
    a.push_back(0);
    while(b.size() < a.size()) {
        b.push_back(0);
    }
    for(int i=0; i<a.size(); ++i) {
        a[i] += b[i];
        if(a[i] > 10) {
            ++a[i+1];
            a[i] -= 10;
        }
    }
    while(!a.empty() && a.back() == 0) {
        a.pop_back();
    }
    return a;
}

vector<int> substractBig(vector<int> a, vector<int> b) {
    while(b.size() < a.size()) {
        b.push_back(0);
    }
    for(int i=0; i<a.size(); ++i) {
        a[i] -= b[i];
        if(a[i] < 0) {
            --a[i+1];
            a[i] += 10;
        }
    }
    while(!a.empty() && a.back() == 0) {
        a.pop_back();
    }
    return a;
}

bool lessBig(const vector<int> &a, const vector<int> &b) {
    if(a.size() != b.size()) {
        return a.size() < b.size();
    }
    for(int i=a.size() - 1; i>=0; --i) {
        if(a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false;
}

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
vector<int> zero;
int idx = 0;

struct Treap {
    Treap *l, *r;
    int key, pri;
    vector<int> sum;
    Treap(int _key) {
        l = r = NULL;
        pri = mt();
        key = _key;
        sum = v[_key];
    }
    ~Treap() {
        delete l;
        delete r;
    }
};

inline vector<int> &getSum(Treap *t) {return t ? t->sum : zero;}

void updateTreap(Treap *t) {
    t->sum = addBig(addBig(getSum(t->l), v[t->key]), getSum(t->r));
}

Treap* mergeTreap(Treap *a, Treap *b) {
    if(!a) return b;
    if(!b) return a;
    if(a->pri > b->pri) {
        a->r = mergeTreap(a->r, b);
        updateTreap(a);
        return a;
    } else {
        b->l = mergeTreap(a, b->l);
        updateTreap(b);
        return b;
    }
}

pair<Treap*, Treap*> splitTreap(Treap *t, vector<int> sum) {
    if(!t) return {NULL, NULL};
    if(!lessBig(getSum(t->l), sum)) {
        auto [t1, t2] = splitTreap(t->l, sum);
        t->l = t2;
        updateTreap(t);
        return {t1, t};
    } else {
        sum = substractBig(sum, getSum(t->l));
        sum = substractBig(sum, v[t->key]);
        auto [t1, t2] = splitTreap(t->r, sum);
        t->r = t1;
        updateTreap(t);
        return {t, t2};
    }
}

void dfsTreap(Treap *t) {
    if(!t) return;
    dfsTreap(t->l);
    p[t->key] = ++idx;
    dfsTreap(t->r);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; ++i) {
        string str; cin>>str;
        v[i] = getBig(str);
    }
    for(int i=n; i>1; --i) {
        v[i] = substractBig(v[i], v[i-1]);
    }
    Treap *t = new Treap(1);
    for(int i=2; i<=n; ++i) {
        vector<int> sum = substractBig(v[i], getBig("1"));
        auto [t1, t2] = splitTreap(t, sum);
        t = mergeTreap(mergeTreap(t1, new Treap(i)), t2);
    }
    dfsTreap(t);
//    delete t;
    for(int i=1; i<=n; ++i) {
        cout<<p[i]<<' ';
    }
    return 0;
}

• Subtask 1: 0 / 100