oj.uz

Submission #62262

# Submission time Handle Problem Language Result Execution time Memory
62262 2018-07-28T00:42:56 Z Benq Permutation Recovery (info1cup17_permutation) C++11
100 / 100
 3926 ms 124352 KB 
#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 = 300;
 
int N, ans[MX];
ll cum[MX], 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 % (2*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

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct
5 Correct 1338 ms 5868 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct
5 Correct 1338 ms 5868 KB Output is correct
6 Correct 2599 ms 9360 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct
5 Correct 1338 ms 5868 KB Output is correct
6 Correct 2599 ms 9360 KB Output is correct
7 Correct 2688 ms 9360 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct
5 Correct 1338 ms 5868 KB Output is correct
6 Correct 2599 ms 9360 KB Output is correct
7 Correct 2688 ms 9360 KB Output is correct
8 Correct 1911 ms 9360 KB Output is correct
9 Correct 3358 ms 12324 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 612 KB Output is correct
3 Correct 8 ms 612 KB Output is correct
4 Correct 8 ms 612 KB Output is correct
5 Correct 1338 ms 5868 KB Output is correct
6 Correct 2599 ms 9360 KB Output is correct
7 Correct 2688 ms 9360 KB Output is correct
8 Correct 1911 ms 9360 KB Output is correct
9 Correct 3358 ms 12324 KB Output is correct
10 Correct 3926 ms 124352 KB Output is correct