oj.uz

Submission #98474

# Submission time Handle Problem Language Result Execution time Memory
98474 2019-02-23T18:30:34 Z keko37 Permutation Recovery (info1cup17_permutation) C++14
60 / 100
 4000 ms 4732 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long llint;

const int MAXN = 70005;
const int S = 400;

int n;
llint d[MAXN], sol[MAXN], fen[MAXN], p[MAXN];
string prosli, curr;
llint m1 = 1000000009, b1 = 10;
deque <llint> v[S + 5];
unordered_set <llint> st[S + 5];
llint ofs[S + 5];

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 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;
    }
    d[ind] = h;
}

inline llint add (llint a, llint b) {
    a += b;
    if (a >= m1) a -= m1;
    return a;
}

int ubaci (llint val) {
    int res = 0;
    int lim = (n + S - 1) / S + 1;
    for (int i=0; i<=lim; i++) {
        llint pise = val - 1 - ofs[i];
        if (pise < 0) pise += m1;
        if (st[i].find(pise) != st[i].end()) {
            st[i].clear();
            deque <llint> e;
            bool naso = 0;
            for (int j=0; j<v[i].size(); j++) {
                if (naso) {
                    llint dodaj = add(v[i] [j], val);
                    e.push_back(dodaj);
                    st[i].insert(dodaj);
                } else {
                    e.push_back(v[i] [j]);
                    st[i].insert(v[i] [j]);
                }
                if (!naso && v[i] [j] == pise) {
                    naso = 1;
                    res = S * i + j;
                    pise = add(pise, val);
                    e.push_back(pise);
                    st[i].insert(pise);
                }
            }
            v[i] = e;
            for (int j = i+1; j <= lim; j++) {
                ofs[j] = add(ofs[j], val);
            }
            int curr = i;
            while (v[curr].size() > S) {
                llint kraj = v[curr].back();
                st[curr].erase(kraj);
                v[curr].pop_back();
                llint novo = (kraj + ofs[curr] - ofs[curr+1] + m1);
                while (novo >= m1) novo -= m1;
                v[curr+1].push_front(novo);
                st[curr+1].insert(novo);
                curr++;
            }
            break;
        }
    }
    return res;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    v[0].push_back(0);
    st[0].insert(0);
    prosli = "0";
    for (int i=1; i<=n; i++) {
        cin >> curr;
        sub(curr, prosli, i);
        swap(prosli, curr);
        sol[i] = ubaci(d[i]);
    }
    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;
}

Compilation message

permutation.cpp: In function 'int ubaci(llint)':
permutation.cpp:70:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0; j<v[i].size(); j++) {
                           ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct
5 Correct 2600 ms 4536 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct
5 Correct 2600 ms 4536 KB Output is correct
6 Execution timed out 4083 ms 4732 KB Time limit exceeded

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct
5 Correct 2600 ms 4536 KB Output is correct
6 Execution timed out 4083 ms 4732 KB Time limit exceeded

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct
5 Correct 2600 ms 4536 KB Output is correct
6 Execution timed out 4083 ms 4732 KB Time limit exceeded

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 13 ms 768 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 16 ms 768 KB Output is correct
5 Correct 2600 ms 4536 KB Output is correct
6 Execution timed out 4083 ms 4732 KB Time limit exceeded