Submission #62262

#	Time	Username	Problem	Language	Result	Execution time	Memory
62262		Benq	Permutation Recovery (info1cup17_permutation)	C++11	100 / 100	3926 ms	124352 KiB

Main

#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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 7 / 7
• Subtask 7: 16 / 16
• Subtask 8: 6 / 6