oj.uz

답안 #199340

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199340 2020-01-31T12:29:15 Z Pankin Permutation Recovery (info1cup17_permutation) C++14
100 / 100
 853 ms 18936 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 305 ms 4104 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 305 ms 4104 KB Output is correct
6 Correct 701 ms 7144 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 305 ms 4104 KB Output is correct
6 Correct 701 ms 7144 KB Output is correct
7 Correct 495 ms 7032 KB Output is correct

Subtask #7
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 305 ms 4104 KB Output is correct
6 Correct 701 ms 7144 KB Output is correct
7 Correct 495 ms 7032 KB Output is correct
8 Correct 607 ms 1936 KB Output is correct
9 Correct 627 ms 6392 KB Output is correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 305 ms 4104 KB Output is correct
6 Correct 701 ms 7144 KB Output is correct
7 Correct 495 ms 7032 KB Output is correct
8 Correct 607 ms 1936 KB Output is correct
9 Correct 627 ms 6392 KB Output is correct
10 Correct 853 ms 18936 KB Output is correct