oj.uz

Submission #118566

# Submission time Handle Problem Language Result Execution time Memory
118566 2019-06-19T08:35:57 Z eohomegrownapps Gondola (IOI14_gondola) C++14
100 / 100
 90 ms 8764 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

long long m=1000000009;

long long mexp(long long a, long long b){
    if (b==0){
        return 1;
    }
    if (b%2==0){
        long long sqr = mexp(a,b/2);
        return (sqr*sqr)%m;
    } else {
        return (mexp(a,b-1)*a)%m;
    }
}

int valid(int n, int inputSeq[]) {
    map<long long,bool> visited;
    long long first = -1;
    bool flag = false;
    for (long long i = 0; i<n; i++){
        if (visited[inputSeq[i]]){
            return 0;
        }
        visited[inputSeq[i]]=true;
        if (inputSeq[i]<=n&&flag==false){
            first=i;
            flag=true;
        }
    }
    if (first==-1){
        return 1;
    }
    long long pt = inputSeq[first];
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (inputSeq[im]!=pt&&inputSeq[im]<=n){
            return 0;
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    long long first = -1;
    for (long long i = 0; i<n; i++){
        if (gondolaSeq[i]<=n){
            first=i;
            break;
        }
    }
    vector<pair<long long,long long> > gondolas;
    //first: new number; second actual number
    long long pt;
    if (first==-1){
        pt=1;
        first=0;
    } else {
        pt=gondolaSeq[first];
    }
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (gondolaSeq[im]>n){
            gondolas.push_back(make_pair(gondolaSeq[im],pt));
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    sort(gondolas.begin(),gondolas.end());
    long long point = 0;
    long long current = n+1; //index of gondola being replaced
    long long numgondolas = 0;
    vector<long long> newname(n+1);
    for (long long i = 0; i<=n; i++){
        newname[i]=i;
    }
    while (point<gondolas.size()){
        while (current<=gondolas[point].first){
            replacementSeq[numgondolas]=newname[gondolas[point].second];
            newname[gondolas[point].second]=current;
            numgondolas++;
            current++;
        }
        point++;
    }
    return numgondolas;
}

int countReplacement(int n, int inputSeq[]) {
    map<long long,bool> visited;
    long long first = -1;
    bool flag = false;
    bool small=true;
    for (long long i = 0; i<n; i++){
        if (visited[inputSeq[i]]){
            return 0;
        }
        visited[inputSeq[i]]=true;
        if (inputSeq[i]<=n&&flag==false){
            first=i;
            flag=true;
        }
        if (inputSeq[i]>n){
            small=false;
        }
    }
    if (small){
        return 1;
    }
    bool noneSmall = false;
    if (first==-1){
        noneSmall=true; //no gondolas <=n
    }
    
    vector<long long> gondolas;
    //first: new number; second actual number
    long long pt;
    if (first==-1){
        pt=1;
        first=0;
    } else {
        pt=inputSeq[first];
    }
    for (long long i = first; i<first+n; i++){
        long long im = i%n;
        if (inputSeq[im]!=pt&&inputSeq[im]<=n){
            return 0;
        }
        if (inputSeq[im]>n){
            gondolas.push_back(inputSeq[im]);
        }
        pt++;
        if (pt>n){
            pt=1;
        }
    }
    sort(gondolas.begin(),gondolas.end());
    long long total = 1;
    long long prev = n;
    long long numleft = gondolas.size();
    for (auto p : gondolas){
        total*=mexp(numleft,p-prev-1);
        total%=m;
        numleft--;
        prev=p;
    }
    if (noneSmall){
        total*=n;
        total%=m;
    }
    return total;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (point<gondolas.size()){
            ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 21 ms 3072 KB Output is correct
7 Correct 12 ms 1280 KB Output is correct
8 Correct 40 ms 5464 KB Output is correct
9 Correct 12 ms 1920 KB Output is correct
10 Correct 47 ms 6264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 428 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 20 ms 2944 KB Output is correct
7 Correct 13 ms 1152 KB Output is correct
8 Correct 40 ms 5536 KB Output is correct
9 Correct 12 ms 1920 KB Output is correct
10 Correct 47 ms 6392 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 23 ms 2944 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 60 ms 6604 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 11 ms 1792 KB Output is correct
12 Correct 13 ms 1920 KB Output is correct
13 Correct 17 ms 1904 KB Output is correct
14 Correct 11 ms 1708 KB Output is correct
15 Correct 20 ms 2392 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 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 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 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 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 69 ms 6400 KB Output is correct
10 Correct 48 ms 5368 KB Output is correct
11 Correct 18 ms 2304 KB Output is correct
12 Correct 24 ms 2684 KB Output is correct
13 Correct 7 ms 896 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 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 384 KB Output is correct
7 Correct 2 ms 476 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 64 ms 6392 KB Output is correct
10 Correct 56 ms 5596 KB Output is correct
11 Correct 20 ms 2324 KB Output is correct
12 Correct 24 ms 2684 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 77 ms 7924 KB Output is correct
15 Correct 90 ms 8764 KB Output is correct
16 Correct 14 ms 2048 KB Output is correct
17 Correct 53 ms 5884 KB Output is correct
18 Correct 30 ms 3700 KB Output is correct