Submission #1315751

#TimeUsernameProblemLanguageResultExecution timeMemory
1315751andrei_nPermutation Recovery (info1cup17_permutation)C++20
0 / 100
72 ms764 KiB
#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;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    assert(n <= 700);
    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]);
    }
    p[1] = 1;
    vector<int> ord = {1};
    for(int i=2; i<=n; ++i) {
        vector<int> sum = substractBig(v[i], getBig("1"));
        int j = 0;
        while(sum.size() != 0) {
            sum = substractBig(sum, v[ord[j]]);
            ++j;
        }
        p[i] = j + 1;
        for(int k=j; k<ord.size(); ++k) {
            ++p[ord[k]];
        }
        ord.insert(ord.begin() + j, i);
    }
    for(int i=1; i<=n; ++i) {
        cout<<p[i]<<' ';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...