oj.uz

Submission #430977

# Submission time Handle Problem Language Result Execution time Memory
430977 2021-06-17T08:40:06 Z errorgorn Gondola (IOI14_gondola) C++17
100 / 100
 42 ms 6244 KB 
#include "gondola.h"
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD=1000000009;

long long qexp(long long i,long long j){
    long long res=1;
    while (j){
        if (j&1) res=(res*i)%MOD;
        i=(i*i)%MOD;
        j>>=1;
    }
    return res;
}

int valid(int n, int in[]) {
    unordered_set<int> s;
    for (int x=0;x<n;x++){
        s.insert(in[x]);
    }

    if (s.size()!=n) return 0;

    int pos;
    for (int x=0;x<n;x++){
        if (in[x]<=n){
            pos=x;
            break;
        }
    }

    for (int x=0;x<n;x++){
        if (in[x]<=n && (in[x]-in[pos]+n)%n!=x-pos) return 0;
    }

    return 1;
}

int replacement(int n, int in[], int res[]) {
    int ret=-1;
    int index=-1;

    int pos=0;
    for (int x=0;x<n;x++){
        if (in[x]<=n){
            pos=(in[x]-x+n-1)%n;
            break;
        }
    }

    for (int x=0;x<n;x++){
        if (in[x]>n){
            res[in[x]-n-1]=(x+pos)%n+1;
        }
        if (in[x]>ret){
            ret=in[x];
            index=x;
        }
    }

    index=(index+pos)%n+1;

    for (int x=0;x<ret-n;x++){
        if (res[x]==0){
            res[x]=index;
            index=x+n+1;
        }
    }
    if (ret-n>=0) res[ret-n-1]=index;
    return ret-n;
}

int countReplacement(int n, int in[]) {
    if (!valid(n,in)) return 0;
    vector<int> v;
    long long ans=1;
    v.push_back(n);
    for (int x=0;x<n;x++){
        if (in[x]>n) v.push_back(in[x]);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());

    for (int x=1;x<v.size();x++){
        ans=(ans*qexp(x,v[x-1]-v[x]-1))%MOD;
    }

    for (int x=0;x<n;x++) if (in[x]<=n) return ans;
    return (ans*n)%MOD;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:25:17: warning: comparison of integer expressions of different signedness: 'std::unordered_set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     if (s.size()!=n) return 0;
      |         ~~~~~~~~^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int x=1;x<v.size();x++){
      |                  ~^~~~~~~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:36:35: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |         if (in[x]<=n && (in[x]-in[pos]+n)%n!=x-pos) return 0;
      |                                   ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 8 ms 1900 KB Output is correct
7 Correct 20 ms 3292 KB Output is correct
8 Correct 16 ms 3400 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 18 ms 3852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 9 ms 1836 KB Output is correct
7 Correct 19 ms 3300 KB Output is correct
8 Correct 16 ms 3420 KB Output is correct
9 Correct 6 ms 1484 KB Output is correct
10 Correct 18 ms 3868 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 10 ms 1796 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 25 ms 5208 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 10 ms 940 KB Output is correct
12 Correct 12 ms 1104 KB Output is correct
13 Correct 13 ms 1228 KB Output is correct
14 Correct 10 ms 972 KB Output is correct
15 Correct 21 ms 2204 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 268 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 29 ms 4024 KB Output is correct
10 Correct 22 ms 3428 KB Output is correct
11 Correct 8 ms 1612 KB Output is correct
12 Correct 11 ms 1708 KB Output is correct
13 Correct 3 ms 588 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 37 ms 4004 KB Output is correct
10 Correct 27 ms 3420 KB Output is correct
11 Correct 9 ms 1612 KB Output is correct
12 Correct 10 ms 1704 KB Output is correct
13 Correct 3 ms 612 KB Output is correct
14 Correct 35 ms 4616 KB Output is correct
15 Correct 42 ms 6244 KB Output is correct
16 Correct 7 ms 1228 KB Output is correct
17 Correct 26 ms 3716 KB Output is correct
18 Correct 15 ms 2216 KB Output is correct