Submission #199340

#	Time	Username	Problem	Language	Result	Execution time	Memory
199340		Pankin	Permutation Recovery (info1cup17_permutation)	C++14	100 / 100	853 ms	18936 KiB

Main

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

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<ll, ll>

const ll INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const ll mod = 362064680345377;
const ll P = 10;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(ll x, ll y, ll n, ll m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937_64 rng(1999999973);

const ll N = 70000 + 500, K = 320;

cc_hash_table<ll, ll> ch[K];
ll ad[K], p[N], q[N], ans[N], need[N], n;
string s;

signed main() {
    fast_io;

    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> s;
        ll st = 1;
        for (ll j = s.size() - 1; j >= 0; j--) {
            q[i] += (ll)(s[j] - '0') * st;
            q[i] %= mod;
            st = (st * P) % mod;
        }
    }

    ll cursum = 1;
    ans[0] = 1;
    for (ll i = 1; i < n; i++) {
        ans[i] = (q[i] + mod - q[i - 1]) % mod;
    }
    for (ll i = 0; i < n; i++) {
        need[i] = (cursum + mod - ans[i]) % mod;
        cursum = (cursum + ans[i]) % mod;
    }

    for (ll i = 0; i < n; i++) {
        ch[i / K][need[i]]++;
    }

    for (ll i = n; i >= 1; i--) {
        ll bl;
        for (ll block = (n - 1) / K; block >= 0; block--) {
            if(ch[block].find(ad[block]) != ch[block].end()) {
                bl = block;
                break;
            }
        }

        ll j = min((bl + 1) * K - 1, n - 1);
        while(need[j] != ad[bl] || p[j] != 0)
            j--;
        ch[bl][need[j]]--;
        if (ch[bl][need[j]] == 0)
            ch[bl].erase(need[j]);
        p[j] = i;
        for (ll k = j + 1; k / K == bl && k < n; k++) {
            if (p[k] != 0)
                continue;
            ch[bl][need[k]]--;
            if (ch[bl][need[k]] == 0)
                ch[bl].erase(need[k]);
            need[k] = (need[k] + mod - ans[j]) % mod;
            ch[bl][need[k]]++;
        }
        for (ll k = bl + 1; k <= (n - 1) / K; k++) {
            ad[k] += ans[j];
            ad[k] %= mod;
        }
    }

    for (ll i = 0; i < n; i++) {
        cout << p[i] << " ";
        assert(p[i] != 0);
    }

    return 0;
}

Compilation message (stderr)

permutation.cpp: In function 'int main()':
permutation.cpp:72:12: warning: 'bl' may be used uninitialized in this function [-Wmaybe-uninitialized]
         ll bl;
            ^~

• 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