oj.uz

Submission #635128

# Submission time Handle Problem Language Result Execution time Memory
635128 2022-08-25T12:50:06 Z PoonYaPat Gondola (IOI14_gondola) C++14
100 / 100
 30 ms 2584 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod=1000000009;
int head[250001];


int valid(int n, int s[]) {

    for (int i=0; i<n; ++i) {
        if (s[i]<=n) {
            int val=s[i];
            for (int j=i+1; j<n; ++j) {
                ++val;
                if (val>n) val-=n;
                if (s[j]<=n && s[j]!=val) return 0;
            }
            break;
        }
    }

    sort(s,s+n);
    for (int i=1; i<n; ++i) if (s[i]==s[i-1]) return 0;

  	return 1;
}

int replacement(int n, int s[], int ans[]) {
    int mmax=0,hm,sc=0;
    bool fix=false;
    for (int i=0; i<n; ++i) {
        mmax=max(mmax,s[i]);
        if (s[i]<=n) {
            fix=true;
            if (sc==0) sc=i;
        }
    }

    if (!fix) {
        for (int i=0; i<n; ++i) {
            head[s[i]]=i+1;
        }
    } else {
        int val=s[sc];
        for (int i=sc; i<n; ++i) {
            head[s[i]]=val++;
            if (val>n) val-=n;
        }
      	for (int i=0; i<sc; ++i) {
          	head[s[i]]=val++;
          	if (val>n) val-=n;
        }
    }
    hm=head[mmax];

    int idx=0;
    for (int i=n+1; i<mmax; ++i) {
        if (!head[i]) {
            ans[idx++]=hm;
            hm=i;
        } else {
            ans[idx++]=head[i];
        }
    }
    ans[idx]=hm;

    return mmax-n;
}

ll power(int x, int y) {
    if (y==0) return 1;
    ll a[30],ans=1;
    a[0]=x;

    for (int i=1; i<=30; ++i) {
        ll h=(a[i-1]*a[i-1])%mod;
        a[i]=h;
    }

    for (int i=0; i<=30; ++i) {
        if (y&(1<<i)) {
            ll h=(ans*a[i])%mod;
            ans=h;
        }
    }
    return ans;
}

int countReplacement(int n, int s[]) {
    if (!valid(n,s)) return 0;

    ll ans=1;
    vector<int> v;

    int cnt=n;

    for (int i=0; i<n; ++i) {
        if (s[i]<=n) --cnt;
        else v.push_back(s[i]);
    }

    if (cnt==n) ans=n;

    v.push_back(n);
    sort(v.begin(),v.end());

    for (int i=1; i<v.size(); ++i) {
        ll h=(ans*power(cnt,v[i]-v[i-1]-1))%mod;
        ans=h;
        --cnt;
    }

    return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i=1; i<v.size(); ++i) {
      |                   ~^~~~~~~~~
gondola.cpp: In function 'll power(int, int)':
gondola.cpp:79:13: warning: iteration 29 invokes undefined behavior [-Waggressive-loop-optimizations]
   79 |         a[i]=h;
      |         ~~~~^~
gondola.cpp:77:20: note: within this loop
   77 |     for (int i=1; i<=30; ++i) {
      |                   ~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 6 ms 456 KB Output is correct
7 Correct 7 ms 664 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 14 ms 632 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 452 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 8 ms 468 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 12 ms 596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 11 ms 596 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 7 ms 852 KB Output is correct
12 Correct 9 ms 964 KB Output is correct
13 Correct 9 ms 1492 KB Output is correct
14 Correct 7 ms 820 KB Output is correct
15 Correct 24 ms 2584 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 26 ms 1048 KB Output is correct
10 Correct 15 ms 852 KB Output is correct
11 Correct 7 ms 584 KB Output is correct
12 Correct 9 ms 596 KB Output is correct
13 Correct 2 ms 396 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 18 ms 1000 KB Output is correct
10 Correct 15 ms 940 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 12 ms 596 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 27 ms 1992 KB Output is correct
15 Correct 30 ms 2240 KB Output is correct
16 Correct 6 ms 700 KB Output is correct
17 Correct 20 ms 1520 KB Output is correct
18 Correct 14 ms 1108 KB Output is correct