oj.uz

Submission #760877

# Submission time Handle Problem Language Result Execution time Memory
760877 2023-06-18T20:05:40 Z Khizri Gondola (IOI14_gondola) C++17
100 / 100
 54 ms 6348 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+9)
const int mxn=2e5+5,mxn2=1e6+5;
int n,color[mxn],arr[mxn],sum[mxn2];
ll pw(ll x,ll y){
    if(y==0) return 1;
    ll k=pw(x,y/2);
    if(y%2==0){
        return (k*k)%MOD;
    }
    return ((k*k%MOD)*x)%MOD;
}
int valid(int n, int vr[])
{
    for(int i=0;i<n;i++){
        arr[i]=vr[i];
    }
    set<int>st;
    for(int i=0;i<n;i++){
        st.insert(arr[i]);
    }
    if(st.size()!=n) return 0;
    int k=n+1,idx=0;
    for(int i=0;i<n;i++){
        if(arr[i]>n) continue;
        if(arr[i]<k){
            k=arr[i];
            idx=i;
        }
    }
    for(int i=idx;i<n;i++){
        if(arr[i]>n){
            arr[i]=k;
        }
        if(arr[i]!=k) return 0;
        k++;
        k%=(n+1);
        if(k==0) k++;
    }
    for(int i=0;i<idx;i++){
        if(arr[i]>n){
            arr[i]=k;
        }
        if(arr[i]!=k) return 0;
        k++;
        k%=(n+1);
        if(k==0) k++;
    }
    return 1;
}

//----------------------

int replacement(int n, int arr[], int replacementSeq[])
{
    int k=0,mn=n+1,idx=0;
    for(int i=0;i<n;i++){
        if(arr[i]>k){
            k=arr[i];
        }
        if(arr[i]<mn){
            mn=arr[i];
            idx=i;
        }
    }
    if(mn>n){
        set<pii>st;
        for(int i=0;i<n;i++){
            st.insert({arr[i],i+1});
        }
        int cnt=0;
        int nxt=n;
        for(auto [l,id]:st){
            replacementSeq[cnt++]=id;
            nxt++;
            while(nxt<l){
                replacementSeq[cnt++]=nxt;
                nxt++;
            }
        }
        return cnt;
    }
    for(int i=idx;i<n;i++){
        if(arr[i]>n){
            color[i]=mn;
        }
        else{
            color[i]=arr[i];
        }
        mn++;
        mn%=(n+1);
        if(mn==0) mn++;
    }
    for(int i=0;i<idx;i++){
        if(arr[i]>n){
            color[i]=mn;
        }
        else{
            color[i]=arr[i];
        }
        mn++;
        mn%=(n+1);
        if(mn==0) mn++;
    }
    set<pii>st;
    for(int i=0;i<n;i++){
        if(color[i]<arr[i]){
            st.insert({arr[i],color[i]});
        }
    }
    int cnt=0;
    int nxt=n;
    for(auto [l,id]:st){
        replacementSeq[cnt++]=id;
        nxt++;
        while(nxt<l){
            replacementSeq[cnt++]=nxt;
            nxt++;
        }
    }
    return cnt;
}

//----------------------

int countReplacement(int n, int arr[])
{
    int k=valid(n,arr);
    if(k==0) return k;
    set<int>st;
    int mx=0,mn=n+1;
    for(int i=0;i<n;i++){
        st.insert(arr[i]);
        mx=max(arr[i],mx);
        mn=min(arr[i],mn);
    }
    sort(arr,arr+n);
    ll ans=1;
    for(int i=0;i<n;i++){
        if(arr[i]<=n) continue;
        if(i==0){
            ll cnt=arr[i]-n-1;
            ans=(ans*pw(n-i,cnt))%MOD;
        }
        else{
            ll cnt=arr[i]-max(n,arr[i-1])-1;
            ans=(ans*pw(n-i,cnt))%MOD;
        }
    }
    if(mn>n){
        ans=(ans*n)%MOD;
    }
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:34:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(st.size()!=n) return 0;
      |        ~~~~~~~~~^~~

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 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

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 8 ms 2260 KB Output is correct
7 Correct 19 ms 4012 KB Output is correct
8 Correct 15 ms 4180 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 19 ms 4820 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 1 ms 212 KB Output is correct
6 Correct 8 ms 2336 KB Output is correct
7 Correct 21 ms 4000 KB Output is correct
8 Correct 15 ms 4128 KB Output is correct
9 Correct 5 ms 1492 KB Output is correct
10 Correct 19 ms 4776 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 9 ms 2136 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 23 ms 4964 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 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
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 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 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 340 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 6 ms 852 KB Output is correct
12 Correct 7 ms 956 KB Output is correct
13 Correct 15 ms 2596 KB Output is correct
14 Correct 7 ms 856 KB Output is correct
15 Correct 17 ms 2924 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 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 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
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 39 ms 4320 KB Output is correct
10 Correct 30 ms 3636 KB Output is correct
11 Correct 10 ms 1536 KB Output is correct
12 Correct 13 ms 1768 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 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 38 ms 4244 KB Output is correct
10 Correct 34 ms 3540 KB Output is correct
11 Correct 11 ms 1492 KB Output is correct
12 Correct 13 ms 1816 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 47 ms 4820 KB Output is correct
15 Correct 54 ms 6348 KB Output is correct
16 Correct 8 ms 1364 KB Output is correct
17 Correct 35 ms 4312 KB Output is correct
18 Correct 19 ms 2516 KB Output is correct