oj.uz

Submission #643865

# Submission time Handle Problem Language Result Execution time Memory
643865 2022-09-23T06:54:07 Z WeetHet Permutation Recovery (info1cup17_permutation) C++17
100 / 100
 2758 ms 5964 KB 
/**
 *  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;

struct chash {
    static unsigned long long hash_f(unsigned long long x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    ll operator()(ll x) const { return hash_f(x); }
};

unordered_multiset<ll, chash> 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

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:46:5: note: in expansion of macro 'rep'
   46 |     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:57:5: note: in expansion of macro 'rep'
   57 |     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:62:5: note: in expansion of macro 'rep'
   62 |     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:98:5: note: in expansion of macro 'rep'
   98 |     rep(i, 0, n) cout << p[i] << ' ';
      |     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 632 ms 3688 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 632 ms 3688 KB Output is correct
6 Correct 1351 ms 5960 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 632 ms 3688 KB Output is correct
6 Correct 1351 ms 5960 KB Output is correct
7 Correct 1800 ms 5964 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 632 ms 3688 KB Output is correct
6 Correct 1351 ms 5960 KB Output is correct
7 Correct 1800 ms 5964 KB Output is correct
8 Correct 1176 ms 2632 KB Output is correct
9 Correct 2544 ms 5868 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 16 ms 460 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 632 ms 3688 KB Output is correct
6 Correct 1351 ms 5960 KB Output is correct
7 Correct 1800 ms 5964 KB Output is correct
8 Correct 1176 ms 2632 KB Output is correct
9 Correct 2544 ms 5868 KB Output is correct
10 Correct 2758 ms 5560 KB Output is correct