답안 #62259 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62259	2018-07-28T00:39:51 Z	Benq	Permutation Recovery (info1cup17_permutation)	C++11	60 / 100	2284 ms	12316 KB

permutation

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const ll MOD = 9999999999999937LL;
const ll INF = 1e18;
const int MX = 100001;
const int B = 280;

int N, ans[MX];
ll cum[B], sum[B];
vpl tmp[B];
unordered_set<ll> pos[B];

ll sub(ll a, ll b) { return (a-b+MOD)%MOD; }
ll ad(ll a, ll b) { return (a+b)%MOD; }

void rebuild() {
    vpl al;
    F0R(i,B) {
        al.insert(al.end(),all(tmp[i]));
        tmp[i].clear(); pos[i].clear();
        pos[i].insert(0); 
    }
    F0R(i,B) {
        int l = (ll)sz(al)*i/B, r = (ll)sz(al)*(i+1)/B;
        ll csum = 0;
        FOR(j,l,r) {
            tmp[i].pb(al[j]);
            pos[i].insert(csum);
            csum = ad(csum,al[j].f);
        }
        sum[i] = csum;
    }
}

void insBucket(int num, ll a, pl b) {
    int ind = 0;
    while (a) a = sub(a,tmp[num][ind++].f);
    tmp[num].insert(tmp[num].begin()+ind,b);
    pos[num].clear();
    ll csum = 0;
    for (auto a: tmp[num]) {
        pos[num].insert(csum);
        // cout << "OH " << csum << "\n";
        csum = ad(csum,a.f);
    }
    sum[num] = csum;
}

void ins(ll a, pl b) {
    F0R(i,B) {
        if (pos[i].count(a) || i == B-1) {
            // cout << "HA " << a << " " << i << " " << b.f << " " << b.s << "\n";
            insBucket(i,a,b);
            return;
        } else a = sub(a,sum[i]);
    }
    // cout << "OOPS " << a << "\n";
}

ll input() {
    ll cur = 0;
    string s; cin >> s;
    for (char c: s) cur = (10*cur+(c-'0'))%MOD;
    return cur;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    F0R(i,B) pos[i].insert(0);
    cin >> N;
    FOR(i,1,N+1) {
        cum[i] = input();
        ll des = sub(cum[i],cum[i-1]);
        ins(des-1,{des,i});
        if (i % B == 0) rebuild();
    }
    int co = 0;
    F0R(i,B) for (auto a: tmp[i]) ans[a.s] = ++co;
    FOR(i,1,N+1) cout << ans[i] << " ";
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct
5	Correct	1407 ms	5868 KB	Output is correct

Subtask #5
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct
5	Correct	1407 ms	5868 KB	Output is correct
6	Runtime error	2284 ms	12316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #6
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct
5	Correct	1407 ms	5868 KB	Output is correct
6	Runtime error	2284 ms	12316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #7
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct
5	Correct	1407 ms	5868 KB	Output is correct
6	Runtime error	2284 ms	12316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	5 ms	484 KB	Output is correct
3	Correct	7 ms	520 KB	Output is correct
4	Correct	12 ms	568 KB	Output is correct
5	Correct	1407 ms	5868 KB	Output is correct
6	Runtime error	2284 ms	12316 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #62259

Compilation message