oj.uz

Submission #54512

# Submission time Handle Problem Language Result Execution time Memory
54512 2018-07-03T21:49:23 Z updown1 Gondola (IOI14_gondola) C++17
100 / 100
 217 ms 16364 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, n)
#define ffj For(j, 0, n)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=100000, MOD=1000000009;
 
int valid(int n, int inputSeq[]) {
    set<int> have;
    ffi have.insert(inputSeq[i]);
    if (have.size() != n) return 0;
    int correct[MAXN];
    ffi if (inputSeq[i] <= n) {
        correct[i] = inputSeq[i];
        For (j, i+1, n) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        correct[0] = 1+correct[n-1];
        if (correct[0] == n+1) correct[0] = 1;
        For (j, 1, i) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        break;
    }
    ffi if (inputSeq[i] != correct[i] && inputSeq[i] <= n) return 0;
    return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int correct[MAXN];
    ffi correct[i] = i+1;
    ffi if (gondolaSeq[i] <= n) {
        correct[i] = gondolaSeq[i];
        For (j, i+1, n) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        correct[0] = 1+correct[n-1];
        if (correct[0] == n+1) correct[0] = 1;
        For (j, 1, i) {
            correct[j] = 1+correct[j-1];
            if (correct[j] == n+1) correct[j] = 1;
        }
        break;
    }
    int at = 0;
    int val = 0, save;
    ffi if (gondolaSeq[i] > val) val = gondolaSeq[i], save = i;
    int loc[250001];
    For (i, 0, 250001) loc[i] = -1;
    ffi loc[gondolaSeq[i]] = i;
    For (i, n+1, val+1) {
        if (loc[i] == -1) {
            replacementSeq[at] = correct[save];
            correct[save] = i;
            at++;
        }
        else {
            replacementSeq[at] = correct[loc[i]];
            correct[loc[i]] = i;
            at++;
        }
    }
    return at;
}
int countReplacement(int n, int inputSeq[]) {
    if (valid(n, inputSeq) == 0) return 0;
    ll ret = 1;
    set<int> have;
    int big = 0;
    ffi if (inputSeq[i] > n) have.insert(inputSeq[i]), big = max(big, inputSeq[i]);
    int at = n+1;
    ll base = have.size();
    ll pb[31];
    for (int i: have) {
        int p = i-at;
        pb[0] = base;
        //w<< base s p <<e;
        For (i, 1, 31) pb[i] = pb[i-1]*pb[i-1], pb[i] %= MOD;
        For (i, 0, 31) if (p & (1<<i)) {
            //w<<i s (1<<i) s pb[i]<<e;
            ret *= pb[i];
            ret %= MOD;
        }
        //w<< ret<<e;
        base--;
        at = i+1;
    }
    bool small = false;
    ffi if (inputSeq[i] <= n) small = true;
    if (!small) ret *= n, ret %= MOD;
    return ret;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (have.size() != n) return 0;
         ~~~~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:66:46: warning: 'save' may be used uninitialized in this function [-Wmaybe-uninitialized]
             replacementSeq[at] = correct[save];
                                  ~~~~~~~~~~~~^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 3 ms 584 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 2 ms 644 KB Output is correct
4 Correct 3 ms 660 KB Output is correct
5 Correct 3 ms 664 KB Output is correct
6 Correct 22 ms 2952 KB Output is correct
7 Correct 50 ms 4752 KB Output is correct
8 Correct 41 ms 5784 KB Output is correct
9 Correct 13 ms 5784 KB Output is correct
10 Correct 43 ms 7028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7028 KB Output is correct
2 Correct 2 ms 7028 KB Output is correct
3 Correct 2 ms 7028 KB Output is correct
4 Correct 2 ms 7028 KB Output is correct
5 Correct 3 ms 7028 KB Output is correct
6 Correct 20 ms 7028 KB Output is correct
7 Correct 49 ms 7028 KB Output is correct
8 Correct 35 ms 7524 KB Output is correct
9 Correct 14 ms 7524 KB Output is correct
10 Correct 42 ms 8804 KB Output is correct
11 Correct 2 ms 8804 KB Output is correct
12 Correct 2 ms 8804 KB Output is correct
13 Correct 28 ms 8804 KB Output is correct
14 Correct 3 ms 8804 KB Output is correct
15 Correct 67 ms 9788 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9788 KB Output is correct
2 Correct 2 ms 9788 KB Output is correct
3 Correct 3 ms 9788 KB Output is correct
4 Correct 3 ms 9788 KB Output is correct
5 Correct 3 ms 9788 KB Output is correct
6 Correct 3 ms 9788 KB Output is correct
7 Correct 2 ms 9788 KB Output is correct
8 Correct 2 ms 9788 KB Output is correct
9 Correct 115 ms 11760 KB Output is correct
10 Correct 77 ms 11760 KB Output is correct
11 Correct 31 ms 11760 KB Output is correct
12 Correct 40 ms 11760 KB Output is correct
13 Correct 10 ms 11760 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11760 KB Output is correct
2 Correct 3 ms 11760 KB Output is correct
3 Correct 3 ms 11760 KB Output is correct
4 Correct 3 ms 11760 KB Output is correct
5 Correct 3 ms 11760 KB Output is correct
6 Correct 2 ms 11760 KB Output is correct
7 Correct 3 ms 11760 KB Output is correct
8 Correct 3 ms 11760 KB Output is correct
9 Correct 110 ms 13040 KB Output is correct
10 Correct 86 ms 13040 KB Output is correct
11 Correct 35 ms 13040 KB Output is correct
12 Correct 38 ms 13040 KB Output is correct
13 Correct 11 ms 13040 KB Output is correct
14 Correct 164 ms 14912 KB Output is correct
15 Correct 217 ms 16364 KB Output is correct
16 Correct 26 ms 16364 KB Output is correct
17 Correct 132 ms 16364 KB Output is correct
18 Correct 54 ms 16364 KB Output is correct