Submission #200017

#	Time	Username	Problem	Language	Result	Execution time	Memory
200017		Bagritsevich_Stepan	Permutation Recovery (info1cup17_permutation)	C++14	43 / 100	330 ms	11352 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;
ll diff[maxn], need[maxn], push[maxn];
unordered_map < ll, int > st[maxn];
bool stat[maxn];
int ans[maxn];

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 = 1;
    for (int i = 0; i < n; i++) {
        need[i] = (h_sum - diff[i] + MOD) % MOD;
        st[i / len][need[i]] = i;
        
        h_sum = (h_sum + diff[i]) % MOD;
    }
    
    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]];
                break;
            }
        }
        
        ans[pos] = num;
        stat[pos] = false;
        int segm_ind = pos / len, l = segm_ind * len, r = min(n, l + len);
        
        st[segm_ind].clear();
        for (int i = l; i < r; i++) {
            if (!stat[i]) continue;
            
            if (i > pos) need[i] = (need[i] - diff[pos] + MOD) % MOD;
            st[segm_ind][need[i]] = i;
        }
            
        for (int ind = segm_ind + 1; ind <= max_segm_ind; ind++)
            push[ind] = (push[ind] + diff[pos]) % MOD;
    }
    
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

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