oj.uz

Submission #586976

# Submission time Handle Problem Language Result Execution time Memory
586976 2022-07-01T07:11:26 Z krit3379 Gondola (IOI14_gondola) C++17
100 / 100
 66 ms 6092 KB 
#include<bits/stdc++.h>
using namespace std;
#include "gondola.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

int valid(int n, int a[]){
    int i;
    long long mod=1e18;
    set<int> s;
    for(i=0;i<n;i++){
        if(s.count(a[i]))return 0;
        s.insert(a[i]);
        if(a[i]>n)continue;
        if(mod==1e18)mod=(i-a[i]+n)%n;
        else if(mod!=(i-a[i]+n)%n)return 0;
    }
    return 1;
}

int replacement(int n, int a[], int b[]){
    int i,j,now,last,cnt;
    vector<pair<int,int>> v;
    for(i=0;i<n;i++)if(a[i]>n)v.push_back({a[i],i});
    for(i=0;i<n;i++){
        if(a[i]<=n){
            now=a[i];
            for(j=i+1;j<n;j++){
                now++;
                if(now==n+1)now=1;
                a[j]=now;
            }
            for(j=0;j<i;j++){
                now++;
                if(now==n+1)now=1;
                a[j]=now;
            }
            break;
        }
    }
    if(i==n)for(i=0;i<n;i++)a[i]=i+1;
    sort(v.begin(),v.end());
    i=0;
    last=n;
    for(auto [now,x]:v){
        cnt=now-last;
        while(cnt--)b[i++]=a[x],a[x]=i+n;
        last=now;
    }
    return i;
}

long long mod=1e9+9;

long long bp(long long a,long long b){
    if(b==0)return 1;
    long long temp=bp(a,b/2);
    if(b%2)return temp*temp%mod*a%mod;
    return temp*temp%mod;
}

int countReplacement(int n, int a[]){
    int i,len,last;
    long long ans=1;
    vector<int> v;
    if(!valid(n,a))return 0;
    for(i=0;i<n;i++)if(a[i]>n)v.push_back(a[i]);
    sort(v.begin(),v.end());
    len=v.size();
    last=n;
    for(i=0;i<len;i++){
        ans=ans*bp(len-i,v[i]-last-1)%mod;
        last=v[i];
    }
    if(len==n)ans=ans*n%mod;
    return ans;
}

Subtask #1
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 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 0 ms 212 KB Output is correct
6 Correct 12 ms 2132 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 24 ms 3832 KB Output is correct
9 Correct 8 ms 1364 KB Output is correct
10 Correct 34 ms 4488 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 13 ms 2108 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 25 ms 3880 KB Output is correct
9 Correct 7 ms 1364 KB Output is correct
10 Correct 31 ms 4520 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 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 8 ms 584 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 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 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 0 ms 212 KB Output is correct
2 Correct 0 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 8 ms 596 KB Output is correct
12 Correct 8 ms 596 KB Output is correct
13 Correct 12 ms 1252 KB Output is correct
14 Correct 7 ms 568 KB Output is correct
15 Correct 17 ms 2248 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 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

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 1 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
9 Correct 40 ms 4044 KB Output is correct
10 Correct 27 ms 3332 KB Output is correct
11 Correct 10 ms 1364 KB Output is correct
12 Correct 12 ms 1620 KB Output is correct
13 Correct 3 ms 596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 34 ms 4000 KB Output is correct
10 Correct 28 ms 3276 KB Output is correct
11 Correct 10 ms 1344 KB Output is correct
12 Correct 13 ms 1624 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 45 ms 5300 KB Output is correct
15 Correct 66 ms 6092 KB Output is correct
16 Correct 13 ms 1364 KB Output is correct
17 Correct 34 ms 4028 KB Output is correct
18 Correct 17 ms 2464 KB Output is correct