Submission #98434

#	Time	Username	Problem	Language	Result	Execution time	Memory
98434		keko37	Permutation Recovery (info1cup17_permutation)	C++14	0 / 100	2 ms	384 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 70005;

int n;
int sol[MAXN], fen[MAXN], p[MAXN];
string prosli, curr;
llint m1 = 1000000007, b1 = 31337;
unordered_map <llint, int> mp;

void ubaci (int x, int k) {
    for (; x < MAXN; x += x&-x) fen[x] += k;
}

int kth (int k) {
    int x = 0, curr = 0;
    for (int pot = 16; pot >= 0; pot--) {
        if (x + (1<<pot) < MAXN && curr + fen[x + (1<<pot)] < k) {
            x += (1 << pot);
            curr += fen[x];
        }
    }
    return x+1;
}

void add (string & a, int ind) {
    string s = a;
    int lena = a.size();
    bool naso = 0;
    for (int i=lena-1; i>=0; i--) {
        s[i]++;
        if (s[i] <= '9') {
            naso = 1;
            break;
        }
        s[i] = '0';
    }
    llint h = 0;
    if (!naso) h = 1;
    for (int i=0; i<lena; i++) {
        h = (h * b1 + s[i] - '0') % m1;
    }
    mp[h] = ind;
}

void sub (string & a, string & b, int ind) {
    int lena = a.size(), lenb = b.size();
    string s = a;
    int carry = 0;
    int pos = lena - 1;
    for (int i=lena-1; i>=0; i--) {
        int x = a[i] - '0', y, val;
        if (lenb - lena + i >= 0) y = b[lenb - lena + i] - '0'; else y = 0;
        val = x - y - carry;
        carry = 0;
        if (val < 0) carry = 1, val += 10;
        s[pos] = val + '0';
        pos--;
    }
    llint h = 0;
    for (int i=0; i<lena; i++) {
        h = (h * b1 + s[i] - '0') % m1;
    }
    sol[ind] = mp[h];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    prosli = "0";
    for (int i=1; i<=n; i++) {
        cin >> curr;
        add(prosli, i-1);
        sub(curr, prosli, i);
        swap(prosli, curr);
    }
    for (int i=1; i<=n; i++) {
        ubaci(i, 1);
    }
    for (int i=n; i>=1; i--) {
        p[i] = kth(sol[i] + 1);
        ubaci(p[i], -1);
    }
    for (int i=1; i<=n; i++) {
        cout << p[i] << " ";
    }
    return 0;
}

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