Submission #643863

#	Time	Username	Problem	Language	Result	Execution time	Memory
643863		WeetHet	Permutation Recovery (info1cup17_permutation)	C++17	100 / 100	2387 ms	116976 KiB

Main

/**
 *  author: WeetHet
 *  created: 18.09.22 17:53:35
**/
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include "bits/stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
using namespace std;
#define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr ll MOD = 323102415747173;
constexpr int MAX_N = 7e4 + 5, B = 333;

unordered_multiset<ll> bk[B];
ll p[MAX_N], delta[MAX_N], aux[MAX_N], add[B];

ll mod(ll x) {
    return x - (x >= MOD) * MOD;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(ios::failbit);

    int n;
    cin >> n;

    ll last = 0;
    rep(i, 0, n) {
        string s;
        cin >> s;

        ll cur = 0;
        for (auto c: s)
            cur = (cur * 10 + c - '0') % MOD;
        delta[i] = mod(cur - last + MOD);
        last = cur;
    }

    rep(i, 0, n) {
        bk[i / B].insert(delta[i]);
        aux[i] = delta[i];
    }

    rep(T, 1, n + 1) {
        int bl = (n - 1) / B;
        while (bl >= 0) {
            ll cur = mod(add[bl] + 1);
            if (bk[bl].find(cur) != bk[bl].end()) break;
            bl -= 1;
        }

        int pos;
        for (pos = min(n - 1, (bl + 1) * B - 1); pos >= bl * B; pos--) {
            if (p[pos] != 0) continue;
            ll cur = mod(aux[pos] - add[bl] + MOD);
            if (cur == 1) break;
        }
        p[pos] = T;

        bk[bl].erase(bk[bl].find(aux[pos]));
        for (int j = pos + 1; j < min(n, (bl + 1) * B); j++) {
            if (p[j] != 0) continue;
            bk[bl].erase(bk[bl].find(aux[j]));
            aux[j] = mod(aux[j] - delta[pos] + MOD);
            bk[bl].insert(aux[j]);
        }
        bl += 1;
        while (bl < (n - 1) / B) {
            add[bl] = mod(add[bl] + delta[pos]);
            bl += 1;
        }

        for (int j = bl * B; j < n; j++) {
            if (p[j] != 0) continue;
            bk[bl].erase(bk[bl].find(aux[j]));
            aux[j] = mod(aux[j] - delta[pos] + MOD);
            bk[bl].insert(aux[j]);
        }
    }
    rep(i, 0, n) cout << p[i] << ' ';
    cout << '\n';
}

Compilation message (stderr)

permutation.cpp: In function 'int main()':
permutation.cpp:11:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
      |                               ^
permutation.cpp:36:5: note: in expansion of macro 'rep'
   36 |     rep(i, 0, n) {
      |     ^~~
permutation.cpp:11:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
      |                               ^
permutation.cpp:47:5: note: in expansion of macro 'rep'
   47 |     rep(i, 0, n) {
      |     ^~~
permutation.cpp:11:31: warning: unnecessary parentheses in declaration of 'T' [-Wparentheses]
   11 | #define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
      |                               ^
permutation.cpp:52:5: note: in expansion of macro 'rep'
   52 |     rep(T, 1, n + 1) {
      |     ^~~
permutation.cpp:11:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   11 | #define rep(i, a, b) for (int (i) = (a); (i) < (b); ++(i))
      |                               ^
permutation.cpp:88:5: note: in expansion of macro 'rep'
   88 |     rep(i, 0, n) cout << p[i] << ' ';
      |     ^~~

• 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