Submission #199948

#	Time	Username	Problem	Language	Result	Execution time	Memory
199948		Bagritsevich_Stepan	Permutation Recovery (info1cup17_permutation)	C++14	10 / 100	8 ms	4216 KiB

Main

//#include "/Users/stdc++.h"
#include <bits/stdc++.h>
 
using namespace std;

#define mp make_pair
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair < int, int >
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef long long ll;
typedef long double ld;

const int INF = 2e9;
const ll BIG_INF = 1e18;
const ll MOD = 20000837;

const ll p = 10;
const int maxn = 7e4 + 5;
unordered_map < ll, vector < int > > st[maxn];
ll diff[maxn], val[maxn], push[maxn];
bool stat[maxn];
int ans[maxn];

void insert_key(int ind, ll h, int pos) {
    if (st[ind].find(h) == st[ind].end()) {
        st[ind].insert({h, {pos}});
        return;
    }
    
    st[ind][h].pb(pos);
}

int main() {
    fast_io
    int n;
    cin >> n;
    
    ll last_h = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        
        ll h = 0;
        for (int j = 0; j < sz(s); j++)
            h = (h * p + (s[j] - '0')) % MOD;
        
        diff[i] = (h - last_h + MOD) % MOD;
        last_h = h;
    }

    const int len = (int)sqrt(n) + 1;
    
    ll h_sum = 0;
    for (int i = 0; i < n; i++) {
        val[i] = diff[i] - h_sum - 1;
        insert_key(i / len, val[i], i);
        
        h_sum += diff[i];
    }
    
    for (int i = 0; i < n; i++)
        stat[i] = true;
    
    int max_segm_ind = (n - 1) / len;
    for (int num = n; num > 0; num--) {
        int pos = 0;
        for (int ind = max_segm_ind; ind >= 0; ind--) {
            if (st[ind].find(-push[ind]) != st[ind].end()) {
                pos = st[ind][-push[ind]].back();
                break;
            }
        }
        
        ans[pos] = num;
        stat[pos] = false;
        int segm_ind = pos / len, l = segm_ind * len, r = l + len;
        
        for (int i = pos + 1; i < r; i++)
            if (stat[i])
                val[i] += diff[pos];
        
        st[segm_ind].clear();
        for (int i = l; i < r; i++) {
            if (!stat[i]) continue;
            
            val[i] += push[segm_ind];
            insert_key(segm_ind, val[i], i);
        }
        push[segm_ind] = 0;
            
        for (int ind = segm_ind + 1; ind <= max_segm_ind; ind++)
            push[ind] += diff[pos];
    }
    
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6