답안 #98474 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98474	2019-02-23T18:30:34 Z	keko37	Permutation Recovery (info1cup17_permutation)	C++14	60 / 100	4000 ms	4732 KB

permutation

#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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	640 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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