oj.uz

Submission #164472

# Submission time Handle Problem Language Result Execution time Memory
164472 2019-11-21T02:23:29 Z dantoh000 Gondola (IOI14_gondola) C++14
90 / 100
 1000 ms 8632 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int valid(int n, int inputSeq[]) {
    int anchor[n];
    unordered_set<int> s;
    int last = -1;
    for (int i = 0; i < n; i++){
        s.insert(inputSeq[i]);
        if (inputSeq[i] > n) continue;
        anchor[i] = (i+n-inputSeq[i])%n;
        //printf("%d ",anchor[i]);
        if (last == -1){
            last = anchor[i];
        }
        else{
            if (last != anchor[i]) return 0;
        }
    }
    if (s.size() != n) return 0;
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int l = 0;
    int maxpos = 1;
    unordered_map<int,int> pos;
    for (int i = 0; i < n; i++){
        if (gondolaSeq[maxpos-1] < gondolaSeq[i]) maxpos = i+1;
    }
    l = gondolaSeq[maxpos-1] - n;
    int curseq[n];
    bool can = false;
    for (int i = 0; i < n; i++){
        pos[gondolaSeq[i]] = i+1;
        if (gondolaSeq[i] <= n){
            can = true;
            curseq[i] = gondolaSeq[i];
        }
        else curseq[i] = (curseq[(n+i-1)%n]) % n +1 ;
    }
    for (int i = 0; i < n; i++){
        if (can) curseq[i] = (curseq[(n+i-1)%n]) % n + 1;
        else curseq[i] = i+1;
        pos[curseq[i]] = i+1;
        //printf("%d ",curseq[i]);
    }
    for (int i = 0; i < l; i++){
        if (pos[i+n+1] == 0) pos[i+n+1] = maxpos;
        //printf("replacing %d %d\n",i+n+1,pos[i+n+1]);
        replacementSeq[i] = curseq[pos[i+n+1]-1];
        curseq[pos[i+n+1]-1] = i+n+1;
        pos[replacementSeq[i]] = pos[i+n+1];
    }
    return l;
}

int countReplacement(int n, int inputSeq[]) {
    if (!valid(n,inputSeq)) return 0;
    int mx = *max_element(inputSeq,inputSeq+n);
    ll ans = 1;
    int ct = n;
    unordered_set<int> s;
    for (int i = 0; i < n; i++){
        if (inputSeq[i] <= n) ct--;
        s.insert(inputSeq[i]);
    }
    if (ct == n) ans = n;
    for (int i = n+1; i <= mx; i++){
        if (s.find(i) != s.end()){
            ct--;
        }
        else{
            ans *= ct;
            ans %= 1000000009;
        }
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (s.size() != n) return 0;
         ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 12 ms 2220 KB Output is correct
7 Correct 15 ms 632 KB Output is correct
8 Correct 24 ms 3972 KB Output is correct
9 Correct 8 ms 1400 KB Output is correct
10 Correct 26 ms 4484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 13 ms 2216 KB Output is correct
7 Correct 13 ms 632 KB Output is correct
8 Correct 22 ms 4000 KB Output is correct
9 Correct 8 ms 1400 KB Output is correct
10 Correct 25 ms 4488 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 7 ms 504 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 14 ms 632 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 28 ms 4232 KB Output is correct
12 Correct 31 ms 4744 KB Output is correct
13 Correct 45 ms 5000 KB Output is correct
14 Correct 29 ms 4228 KB Output is correct
15 Correct 74 ms 8632 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 48 ms 4616 KB Output is correct
10 Correct 42 ms 4396 KB Output is correct
11 Correct 23 ms 1528 KB Output is correct
12 Correct 22 ms 2172 KB Output is correct
13 Correct 12 ms 792 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 49 ms 4524 KB Output is correct
10 Correct 40 ms 4348 KB Output is correct
11 Correct 22 ms 1528 KB Output is correct
12 Correct 21 ms 2168 KB Output is correct
13 Correct 11 ms 792 KB Output is correct
14 Execution timed out 1065 ms 5420 KB Time limit exceeded
15 Halted 0 ms 0 KB -