oj.uz

Submission #589247

# Submission time Handle Problem Language Result Execution time Memory
589247 2022-07-04T10:57:34 Z BT21tata Gondola (IOI14_gondola) C++17
100 / 100
 86 ms 11000 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 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

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 3 ms 340 KB Output is correct
7 Correct 11 ms 592 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 7 ms 548 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 3 ms 340 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 7 ms 596 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 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 10 ms 596 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 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 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

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 1 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 580 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Correct 20 ms 2496 KB Output is correct
14 Correct 8 ms 724 KB Output is correct
15 Correct 28 ms 2804 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 1 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 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

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 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 49 ms 6852 KB Output is correct
10 Correct 41 ms 5196 KB Output is correct
11 Correct 15 ms 2796 KB Output is correct
12 Correct 22 ms 3284 KB Output is correct
13 Correct 5 ms 980 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 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 48 ms 6848 KB Output is correct
10 Correct 32 ms 5236 KB Output is correct
11 Correct 14 ms 2744 KB Output is correct
12 Correct 18 ms 3256 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 69 ms 9712 KB Output is correct
15 Correct 86 ms 11000 KB Output is correct
16 Correct 14 ms 2296 KB Output is correct
17 Correct 54 ms 7432 KB Output is correct
18 Correct 27 ms 4292 KB Output is correct