oj.uz

Submission #466580

# Submission time Handle Problem Language Result Execution time Memory
466580 2021-08-19T17:08:11 Z Carmel_Ab1 Gondola (IOI14_gondola) C++17
75 / 100
 27 ms 2660 KB 
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;

#include "gondola.h"
//#include "grader.cpp"
#define pb push_back
#define all(x) x.begin(),x.end()
#define print(x) {for(auto it:x){cout << it << " "; }cout << "\n";}
int valid(int n, int inputSeq[]){
    vi a(n);
    for(int i=0; i<n; i++)
        a[i]=inputSeq[i];
    vi s(a);
    sort(all(s));
    for(int i=0; i<n-1; i++)
        if(s[i]==s[i+1])
            return 0;
    int f=-1;
    for(int i=0; i<n; i++)
        if(a[i]<=n)
            f=i;
    for(int i=0; i<n; i++)
        if(a[i]<=0)
            return 0;
    if(f==-1)return 1;
    for(int i=0,j=a[f]; i<n; j=((j%n) +1),i++){
        int cur=a[(i+f)%n];
        if(cur!=j && cur<=n)
            return 0;
    }
    return 1;
}

int replacement(int n, int a[], int rep[]){
    vi ans,org(n+1);
    int f=-1;
    for(int i=0; i<n; i++)
        if(a[i]<=n)
            f=i;
    if(f==-1)
        for(int i=0; i<n; i++)
            org[i]=i+1;
    else
        for(int i=0,j=a[f]; i<n; j=((j%n) +1),i++){
            int cur=a[(i+f)%n];
            org[(i+f)%n]=j;
        }
    vector<pair<int,int>>s;
    for(int i=0; i<n; i++)
        s.push_back({a[i],i});
    sort(all(s));
    vector<bool>has(250001);
    for(int i=0; i<n; i++)
        has[a[i]]=1;
    for(int i=0,j=n+1; i<n; i++){
        if(s[i].first<=n)continue;
        ans.pb(org[s[i].second]);
        while(!has[j]){
            has[j]=1;
            ans.pb(j);
            j++;
        }
        j++;
    }

    for(int i=0; i<ans.size(); i++)
        rep[i]=ans[i];
    return ans.size();
}
ll power(ll a,ll b,ll m){
    if(b==0)return 1;
    else if(b==1)return a;
    ll r=power(a,b/2,m);
    ll ans=(r*r)%m;
    if(b%2)ans=(ans*a)%m;
    return ans;
}
int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq))
        return 0;
    vi a(n);
    for(int i=0; i<n ;i++)
        a[i]=inputSeq[i];
    sort(all(a));
    const ll m=1e9+9;
    ll ans=1,cnt=0;
    for(int i=0; i<n; i++)
        if(a[i]>n)
            cnt++;
    for(int i=n+1; i<=a.back(); i++){
        if(binary_search(all(a),i))
            cnt--;
        else
            ans=(ans*cnt)%m;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:17: warning: unused variable 'cur' [-Wunused-variable]
   47 |             int cur=a[(i+f)%n];
      |                 ^~~
gondola.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0; i<ans.size(); i++)
      |                  ~^~~~~~~~~~~

Subtask #1
5.0 / 5.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 1 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 1 ms 304 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 1 ms 204 KB Output is correct
6 Correct 8 ms 968 KB Output is correct
7 Correct 16 ms 1740 KB Output is correct
8 Correct 12 ms 1484 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 17 ms 1764 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 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 300 KB Output is correct
6 Correct 8 ms 844 KB Output is correct
7 Correct 17 ms 1796 KB Output is correct
8 Correct 12 ms 1552 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 18 ms 1776 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 7 ms 844 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 17 ms 1748 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 14 ms 2464 KB Output is correct
12 Correct 17 ms 2660 KB Output is correct
13 Correct 18 ms 1836 KB Output is correct
14 Correct 14 ms 2448 KB Output is correct
15 Correct 24 ms 2468 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 1 ms 204 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 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 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

Subtask #9
0 / 15.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 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 27 ms 1660 KB Output is correct
10 Correct 22 ms 1320 KB Output is correct
11 Correct 11 ms 696 KB Output is correct
12 Correct 11 ms 720 KB Output is correct
13 Incorrect 5 ms 332 KB Output isn't correct

Subtask #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 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 27 ms 1612 KB Output is correct
10 Correct 21 ms 1304 KB Output is correct
11 Correct 11 ms 716 KB Output is correct
12 Correct 11 ms 716 KB Output is correct
13 Incorrect 5 ms 428 KB Output isn't correct
14 Halted 0 ms 0 KB -