oj.uz

Submission #200018

# Submission time Handle Problem Language Result Execution time Memory
200018 2020-02-04T21:44:48 Z Bagritsevich_Stepan Permutation Recovery (info1cup17_permutation) C++14
100 / 100
 1673 ms 30552 KB 
//#include "/Users/stdc++.h"
#include <bits/stdc++.h>
 
using namespace std;

#define mp make_pair
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair < int, int >
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef long long ll;
typedef long double ld;

const int INF = 2e9;
const ll BIG_INF = 1e18;
const ll MOD = 9999999999999937LL;

const ll p = 10;
const int maxn = 7e4 + 5;
ll diff[maxn], need[maxn], push[maxn];
unordered_map < ll, int > st[maxn];
bool stat[maxn];
int ans[maxn];

int main() {
    fast_io
    int n;
    cin >> n;
    
    ll last_h = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        
        ll h = 0;
        for (int j = 0; j < sz(s); j++)
            h = (h * p + (s[j] - '0')) % MOD;
        
        diff[i] = (h - last_h + MOD) % MOD;
        last_h = h;
    }

    const int len = (int)sqrt(n) + 1;
    
    ll h_sum = 1;
    for (int i = 0; i < n; i++) {
        need[i] = (h_sum - diff[i] + MOD) % MOD;
        st[i / len][need[i]] = i;
        
        h_sum = (h_sum + diff[i]) % MOD;
    }
    
    for (int i = 0; i < n; i++)
        stat[i] = true;
    
    int max_segm_ind = (n - 1) / len;
    for (int num = n; num > 0; num--) {
        int pos = 0;
        for (int ind = max_segm_ind; ind >= 0; ind--) {
            if (st[ind].find(push[ind]) != st[ind].end()) {
                pos = st[ind][push[ind]];
                break;
            }
        }
        
        ans[pos] = num;
        stat[pos] = false;
        int segm_ind = pos / len, l = segm_ind * len, r = min(n, l + len);
        
        st[segm_ind].clear();
        for (int i = l; i < r; i++) {
            if (!stat[i]) continue;
            
            if (i > pos) need[i] = (need[i] - diff[pos] + MOD) % MOD;
            st[segm_ind][need[i]] = i;
        }
            
        for (int ind = segm_ind + 1; ind <= max_segm_ind; ind++)
            push[ind] = (push[ind] + diff[pos]) % MOD;
    }
    
    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 459 ms 7008 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 459 ms 7008 KB Output is correct
6 Correct 1102 ms 19016 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 459 ms 7008 KB Output is correct
6 Correct 1102 ms 19016 KB Output is correct
7 Correct 1036 ms 20364 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 459 ms 7008 KB Output is correct
6 Correct 1102 ms 19016 KB Output is correct
7 Correct 1036 ms 20364 KB Output is correct
8 Correct 820 ms 30552 KB Output is correct
9 Correct 1425 ms 10112 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Output is correct
2 Correct 8 ms 4216 KB Output is correct
3 Correct 8 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 459 ms 7008 KB Output is correct
6 Correct 1102 ms 19016 KB Output is correct
7 Correct 1036 ms 20364 KB Output is correct
8 Correct 820 ms 30552 KB Output is correct
9 Correct 1425 ms 10112 KB Output is correct
10 Correct 1673 ms 17528 KB Output is correct