oj.uz

Submission #786008

# Submission time Handle Problem Language Result Execution time Memory
786008 2023-07-17T21:56:08 Z Sputnik1234 Gondola (IOI14_gondola) C++14
100 / 100
 67 ms 11936 KB 
#include "gondola.h"
#include <bits/stdc++.h>
typedef long long ll; 
using namespace std;
const ll MOD=1e9+9;
 
map<int,int> hp;
 
int valid(int n, int a[])
{
    int val=-1;
    for(int i=0; i<n; i++)
    {
        if(a[i]<=n)
        {
            if(val==-1)
            {
                val=a[i]+1;
                if(val==n+1) val=1;
            }
            else
            {
                if(a[i]!=val)
                {
                    //cout<<i<<' '<<a[i]<<' '<<val<<endl;
                    return 0;
                }
                else
                {
                    val=a[i]+1;
                    if(val==n+1) val=1;
                }
            }
        }
        else
        {
            if(hp[a[i]]) return 0;
            hp[a[i]]=1;
            if(val!=-1)
            {
                val++;
                if(val==n+1) val=1;
            }
        }
    }
    return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int rep=1, m=0;
    for(int i=0; i<n; i++)
    {
        if(gondolaSeq[i]<=n)
        {
            rep=gondolaSeq[i];
            for(int j=i-1; j>=0; j--)
            {
                rep--;
                if(!rep) rep=n;
            }
            break;
        }
    }
    multiset<pair<int, int>> s;
    for(int i=0; i<n; i++)
    {
        if(rep!=gondolaSeq[i])
        {
            s.insert({gondolaSeq[i], rep});
        }
        rep++;
        if(rep==n+1) rep=1;
    }
    int b=n+1;
    while(s.size())
    {
        int need=(*s.begin()).first;
        int hv=(*s.begin()).second;
        s.erase(s.begin());
        replacementSeq[m++]=hv;
        hv=b++;
        if(need!=hv) s.insert({need, hv});
    }
    return m;
}
 
//----------------------
 
ll pw(ll b, ll p)
{
    if(!p) return 1;
    ll P=pw(b, p>>1);
    if(p&1) return P*P%MOD*b%MOD;
    return P*P%MOD;
}
 
int countReplacement(int n, int inputSeq[])
{
    //cout<<"ok"<<endl<<flush;
    if(!valid(n, inputSeq)) return 0;
    //cout<<"ok"<<endl<<flush;
    ll rep=-1;
    for(int i=0; i<n; i++)
    {
        if(inputSeq[i]<=n)
        {
            rep=inputSeq[i];
            for(int j=i-1; j>=0; j--)
            {
                rep--;
                if(!rep) rep=n;
            }
            break;
        }
    }
    ll ans=1;
    if(rep==-1)
    {
        rep=1;
        ans*=n;
 
    }
    multiset<pair<ll, ll>> s;
    for(int i=0; i<n; i++)
    {
        if(rep!=inputSeq[i])
        {
            s.insert({inputSeq[i], rep});
        }
        rep++;
        if(rep==n+1) rep=1;
    }
    ll b=n+1;
    while(s.size())
    {
        ll need=(*s.begin()).first;
        ll hv=(*s.begin()).second;
        //cout<<s.size()<<' '<<need<<' '<<hv<<' '<<endl<<flush;
        if(need!=hv) ans*=pw(1ll*s.size(), need-b), ans%=MOD;
        b=need+1;
        s.erase(s.begin());
    }
    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 284 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 6 ms 956 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 7 ms 1056 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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 7 ms 1092 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 7 ms 1028 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 3 ms 596 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 7 ms 1108 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 264 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 304 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 308 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 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 308 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 960 KB Output is correct
12 Correct 7 ms 1064 KB Output is correct
13 Correct 17 ms 2644 KB Output is correct
14 Correct 6 ms 980 KB Output is correct
15 Correct 24 ms 3004 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 1 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 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 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
15.0 / 15.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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 40 ms 7316 KB Output is correct
10 Correct 33 ms 5740 KB Output is correct
11 Correct 14 ms 2900 KB Output is correct
12 Correct 18 ms 3424 KB Output is correct
13 Correct 4 ms 1092 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 0 ms 212 KB Output is correct
4 Correct 0 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 7284 KB Output is correct
10 Correct 28 ms 5580 KB Output is correct
11 Correct 13 ms 2900 KB Output is correct
12 Correct 16 ms 3416 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 60 ms 10568 KB Output is correct
15 Correct 67 ms 11936 KB Output is correct
16 Correct 10 ms 2432 KB Output is correct
17 Correct 43 ms 8040 KB Output is correct
18 Correct 23 ms 4672 KB Output is correct