oj.uz

Submission #542064

# Submission time Handle Problem Language Result Execution time Memory
542064 2022-03-25T09:38:55 Z Sho10 Gondola (IOI14_gondola) C++17
100 / 100
 71 ms 13504 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#include "gondola.h"
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000009;
ld const PI=3.14159265359;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int valid(int n,int a[]){
int mn=INF,pos=-1;
map<ll,ll>viz;
for(int i=0;i<n;i++)
{
    viz[a[i]]++;
    if(a[i]<mn){
        mn=a[i];
        pos=i;
    }
}
for(ll i=0;i<n;i++)
{
    if(viz[a[i]]>=2){
        return 0;
    }
}
if(mn>n){
    return 1;
}
int b[200005];
for(int i=0;i<n;i++)
{
    b[i]=a[i];
}
a[0]=b[pos];
ll val=0;
for(ll i=pos+1;i<n;i++)
{
    a[i-pos]=b[i];
    val=i-pos;
}
val++;
for(ll i=0;i<pos;i++)
{
a[val]=b[i];
val++;
}
ll x=a[0];
x++;
b[0]=a[0];
for(ll i=1;i<n;i++)
{
    x%=n;
    if(x==0){
        x=n;
    }
b[i]=x;
x++;
}
for(ll i=1;i<n;i++)
{
    if(b[i]!=a[i]){
        if(a[i]<=n){
            return 0;
        }
    }
}
return 1;
}
int replacement(int n,int a[],int g[]){
int mn=INF,pos=-1;
for(int i=0;i<n;i++)
{
    if(a[i]<mn){
        mn=a[i];
        pos=i;
    }
}
int b[200005],val;
for(int i=0;i<n;i++)
{
    b[i]=a[i];
}
if(mn>n){
    goto Next;
}
a[0]=b[pos];
val=0;
for(ll i=pos+1;i<n;i++)
{
    a[i-pos]=b[i];
    val=i-pos;
}
val++;
for(ll i=0;i<pos;i++)
{
a[val]=b[i];
val++;
}
for(int i=0;i<n;i++)
{
    b[i]=a[i];
}
val=mn;
for(ll i=0;i<n;i++)
{
    ll x=i-mn+1;
    if(x<0){
        x+=n;
    }
    a[i]=b[x];

}
Next:
int mx=0;
ll check=0;
for(ll i=0;i<n;i++)
{
    mx=max(mx,a[i]);
}
 pos=0;
for(ll i=0;i<n;i++)
{
    if(mx==a[i]){
        pos=i+1;
    }
}
map<ll,ll>viz;
for(ll i=0;i<n;i++)
{
    viz[a[i]]=i+1;
}
for(ll i=n+1;i<=mx;i++)
{
if(viz[i]==0||i==mx){
    g[i-n-1]=pos;
pos=i;
}else {
g[i-n-1]=viz[i];
}
}
return mx-n;
}

ll pw(ll a,ll b){
    if(b==0) return 1;
    ll n=pw(a,b/2);
    if(b%2==1){
            return (((n*n)%mod)*a)%mod;
    }else return (n*n)%mod;
}
int countReplacement(int n,int a[]){
if(valid(n,a)==0){
    return 0;
}
int mn=INF,pos=-1;
for(int i=0;i<n;i++)
{
    if(a[i]<mn){
        mn=a[i];
        pos=i;
    }
}
int b[200005],val;
for(int i=0;i<n;i++)
{
    b[i]=a[i];
}
if(mn>n){
    goto Next;
}
a[0]=b[pos];
val=0;
for(ll i=pos+1;i<n;i++)
{
    a[i-pos]=b[i];
    val=i-pos;
}
val++;
for(ll i=0;i<pos;i++)
{
a[val]=b[i];
val++;
}
for(int i=0;i<n;i++)
{
    b[i]=a[i];
}
val=mn;
for(ll i=0;i<n;i++)
{
    ll x=i-mn+1;
    if(x<0){
        x+=n;
    }
    a[i]=b[x];

}
Next:
    vector<ll>v;
    for(ll i=0;i<n;i++)
    {
        if(a[i]>n){
            v.pb(a[i]);
        }
    }
    sort(v.begin(),v.end());
    ll last=n;
    ll ans=1;
    for(ll i=0;i<v.size();i++)
    {
        ans=(ans*pw((v.size()-i),(v[i]-1-last))%mod)%mod;
        last=v[i];
    }
    if(mn>n){
        ans=(ans*n)%mod;
    }
    return ans;
}
/*
int32_t main(){
    ifstream cin("input.in");
int n,a[100005],idk[100005];
cin>>n;
for(int i=0;i<n;i++)
{
    cin>>a[i];
}
cout<<replacement(n,a,idk)<<endl;
}
*/

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:124:4: warning: unused variable 'check' [-Wunused-variable]
  124 | ll check=0;
      |    ^~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:218:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |     for(ll i=0;i<v.size();i++)
      |                ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 15 ms 3660 KB Output is correct
7 Correct 26 ms 5708 KB Output is correct
8 Correct 32 ms 6172 KB Output is correct
9 Correct 10 ms 2644 KB Output is correct
10 Correct 34 ms 6860 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 1076 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 15 ms 3796 KB Output is correct
7 Correct 28 ms 5800 KB Output is correct
8 Correct 30 ms 6188 KB Output is correct
9 Correct 9 ms 2684 KB Output is correct
10 Correct 33 ms 6940 KB Output is correct
11 Correct 1 ms 1072 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 20 ms 3552 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 49 ms 7184 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1072 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 1076 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 2 ms 1328 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1076 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1028 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1364 KB Output is correct
11 Correct 24 ms 6684 KB Output is correct
12 Correct 27 ms 7372 KB Output is correct
13 Correct 38 ms 6856 KB Output is correct
14 Correct 25 ms 6612 KB Output is correct
15 Correct 52 ms 13504 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1844 KB Output is correct
2 Correct 1 ms 1848 KB Output is correct
3 Correct 1 ms 1748 KB Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1748 KB Output is correct
5 Correct 1 ms 1840 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1840 KB Output is correct
9 Correct 51 ms 7116 KB Output is correct
10 Correct 36 ms 6292 KB Output is correct
11 Correct 13 ms 3412 KB Output is correct
12 Correct 17 ms 3768 KB Output is correct
13 Correct 5 ms 2260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1844 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1876 KB Output is correct
9 Correct 54 ms 7216 KB Output is correct
10 Correct 36 ms 6220 KB Output is correct
11 Correct 14 ms 3476 KB Output is correct
12 Correct 17 ms 3768 KB Output is correct
13 Correct 4 ms 2260 KB Output is correct
14 Correct 61 ms 8236 KB Output is correct
15 Correct 71 ms 9036 KB Output is correct
16 Correct 11 ms 3212 KB Output is correct
17 Correct 43 ms 6740 KB Output is correct
18 Correct 24 ms 4468 KB Output is correct