oj.uz

Submission #20818

# Submission time Handle Problem Language Result Execution time Memory
20818 2017-02-16T12:46:19 Z jjwdi0 Gondola (IOI14_gondola) C++11
100 / 100
 69 ms 8680 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define MOD 1000000009
using namespace std;
typedef long long ll;
typedef pair<int, int> pr;

int N;
vector<int> v;
vector<pr> rpc;
map<int, int> same;

ll pow(ll x, int y) {
    if(!y) return 1LL;
    ll u = pow(x, y / 2);
    return y & 1 ? u * u % MOD * x % MOD : u * u % MOD;
}

int valid(int n, int inputSeq[]) {
    N = n;
    int idx = -1;
    for(int i=0; i<N; i++) same[inputSeq[i]]++;
    for(auto it : same) if(it.second > 1) return 0;
    for(int i=0; i<N; i++) {
        if(inputSeq[i] <= N) { idx = i; break; }
    }
    if(idx < 0) return 1;
    int u = inputSeq[idx];
    for(int i=idx; i<idx+N; i++) {
        if(inputSeq[i % N] > N) continue;
        if(inputSeq[i % N] != (u + (i - idx) - 1) % N + 1) return 0;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    N = n;
    int idx = 0, res = 0;
    for(int i=0; i<N; i++) {
        if(gondolaSeq[i] <= N) { idx = i; break; }
    }
    int u = gondolaSeq[idx] > N ? 1 : gondolaSeq[idx];
    for(int i=0; i<N; i++) if(gondolaSeq[i] > N) rpc.push_back(pr(gondolaSeq[i], i));
    sort(all(rpc));
    int p = N + 1;
    for(int i=0; i<sz(rpc); i++) {
        int t;
        if(rpc[i].second >= idx) t = (u + rpc[i].second - idx - 1) % N + 1;
        else t = (u + rpc[i].second + N - idx - 1) % N + 1;
        while(t < rpc[i].first) {
            replacementSeq[res++] = t;
            t = p++;
        }
    }
    return res;
}

int countReplacement(int n, int inputSeq[]) {
    N = n;
    if(!valid(N, inputSeq)) return 0;
    for(int i=0; i<N; i++) if(inputSeq[i] > N) v.push_back(inputSeq[i]);
    sort(all(v));
    ll res = (sz(v) == N ? N : 1LL), m = sz(v);
    int pre = N;
    for(int i=0; i<sz(v); i++) {
        res = res * pow(m, v[i] - pre - 1) % MOD;
        m--, pre = v[i];
    }
    return res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 9 ms 5112 KB Output is correct
7 Correct 36 ms 6432 KB Output is correct
8 Correct 26 ms 6696 KB Output is correct
9 Correct 6 ms 4452 KB Output is correct
10 Correct 33 ms 7356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 13 ms 5112 KB Output is correct
7 Correct 33 ms 6432 KB Output is correct
8 Correct 23 ms 6696 KB Output is correct
9 Correct 6 ms 4452 KB Output is correct
10 Correct 23 ms 7356 KB Output is correct
11 Correct 0 ms 3396 KB Output is correct
12 Correct 0 ms 3396 KB Output is correct
13 Correct 19 ms 5112 KB Output is correct
14 Correct 0 ms 3396 KB Output is correct
15 Correct 43 ms 7488 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 0 ms 3396 KB Output is correct
10 Correct 0 ms 3396 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 0 ms 3396 KB Output is correct
10 Correct 0 ms 3396 KB Output is correct
11 Correct 9 ms 3396 KB Output is correct
12 Correct 6 ms 3396 KB Output is correct
13 Correct 16 ms 3864 KB Output is correct
14 Correct 9 ms 3396 KB Output is correct
15 Correct 19 ms 3864 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 43 ms 7304 KB Output is correct
10 Correct 39 ms 6720 KB Output is correct
11 Correct 13 ms 4644 KB Output is correct
12 Correct 16 ms 4880 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3396 KB Output is correct
2 Correct 0 ms 3396 KB Output is correct
3 Correct 0 ms 3396 KB Output is correct
4 Correct 0 ms 3396 KB Output is correct
5 Correct 0 ms 3396 KB Output is correct
6 Correct 0 ms 3396 KB Output is correct
7 Correct 0 ms 3396 KB Output is correct
8 Correct 0 ms 3396 KB Output is correct
9 Correct 46 ms 7304 KB Output is correct
10 Correct 36 ms 6720 KB Output is correct
11 Correct 13 ms 4644 KB Output is correct
12 Correct 16 ms 4880 KB Output is correct
13 Correct 3 ms 3796 KB Output is correct
14 Correct 59 ms 8172 KB Output is correct
15 Correct 69 ms 8680 KB Output is correct
16 Correct 6 ms 4460 KB Output is correct
17 Correct 43 ms 6844 KB Output is correct
18 Correct 23 ms 5536 KB Output is correct