oj.uz

Submission #199335

# Submission time Handle Problem Language Result Execution time Memory
199335 2020-01-31T12:13:52 Z Pankin Permutation Recovery (info1cup17_permutation) C++14
78 / 100
 1391 ms 6008 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);

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll N = 70000 + 50, K = 300;

unordered_map<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] << " ";

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 708 ms 3536 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 708 ms 3536 KB Output is correct
6 Correct 1391 ms 6008 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 708 ms 3536 KB Output is correct
6 Correct 1391 ms 6008 KB Output is correct
7 Correct 962 ms 5880 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 708 ms 3536 KB Output is correct
6 Correct 1391 ms 6008 KB Output is correct
7 Correct 962 ms 5880 KB Output is correct
8 Execution timed out 433 ms 2284 KB Time limit exceeded (wall clock)
9 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 376 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 708 ms 3536 KB Output is correct
6 Correct 1391 ms 6008 KB Output is correct
7 Correct 962 ms 5880 KB Output is correct
8 Execution timed out 433 ms 2284 KB Time limit exceeded (wall clock)
9 Halted 0 ms 0 KB -