oj.uz

Submission #964312

# Submission time Handle Problem Language Result Execution time Memory
964312 2024-04-16T15:50:19 Z maxFedorchuk Gondola (IOI14_gondola) C++17
100 / 100
 56 ms 6156 KB 
#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
 
int valid(int n, int inputSeq[])
{
    set < int > st;
 
    int p=0;
    for(int i=0;i<n;i++)
    {
        if(inputSeq[i]<=n)
        {
            p=(n+i-inputSeq[i])%n;
        }
 
        st.insert(inputSeq[i]);
    }
 
    if(st.size()!=n)
    {
        return 0;
    }
 
    for(int i=0;i<n;i++)
    {
        if(inputSeq[i]<=n)
        {
            if((n+i-inputSeq[i])%n!=p)
            {
                return 0;
            }
        }
    }
 
    return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int ned_to_be[n],in=-1;
    for(int i=0;i<n;i++)
    {
        if(gondolaSeq[i]<=n)
        {
            ned_to_be[i]=gondolaSeq[i];
            in=i;
            break;
        }
    }
 
    if(in!=-1)
    {
        int nd=ned_to_be[in];
        for(int i=(in+1)%n;i!=in;i=(i+1)%n)
        {
            nd%=n;
            nd++;
 
            ned_to_be[i]=nd;
        }
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            ned_to_be[i]=i+1;
        }
    }
 
    map < int , int > mp;
 
    int mx=0;
    for(int i=0;i<n;i++)
    {
        if(gondolaSeq[i]>mx)
        {
            mx=gondolaSeq[i];
            in=i;
        }
 
        if(gondolaSeq[i]>n)
        {
            mp[gondolaSeq[i]]=ned_to_be[i];
        }
    }
 
    int uk=0;
    for(int i=n+1;i<=mx;i++,uk++)
    {
        if(mp.find(i)==mp.end() || i==mx)
        {
            replacementSeq[uk]=ned_to_be[in];
            ned_to_be[in]=i;
        }
        else
        {
            replacementSeq[uk]=mp[i];
        }
    }
 
    return uk;
}
 
//----------------------
 
const long long MOD=1e9+9;
 
long long binpow(long long a,long long b)
{
    long long rt=1;
 
    while(b)
    {
        if(b&1)
        {
            rt=(rt*a)%MOD;
        }
 
        a=(a*a)%MOD;
        b/=2;
    }
 
    return rt;
}
 
int countReplacement(int n, int inputSeq[])
{
    if(!valid(n,inputSeq))
    {
        return 0;
    }
 
    set < long long > st;
 
    for(long long i=0;i<n;i++)
    {
        if(inputSeq[i]>n)
        {
            st.insert(inputSeq[i]);
        }
    }
 
    long long mun=n,ans=1,k=st.size();
    for(auto u:st)
    {
        //cout<<u<<" "<<k<<" "<<u-mun-1<<"\n";
        ans=(ans*binpow(k,u-mun-1+(k==n)))%MOD;
        k--;
        mun=u;
    }
 
    return ans;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2116 KB Output is correct
7 Correct 22 ms 3676 KB Output is correct
8 Correct 14 ms 3928 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 19 ms 4528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 19 ms 3676 KB Output is correct
8 Correct 15 ms 3932 KB Output is correct
9 Correct 5 ms 1372 KB Output is correct
10 Correct 18 ms 4444 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 9 ms 2136 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 24 ms 4676 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 11 ms 856 KB Output is correct
12 Correct 13 ms 1116 KB Output is correct
13 Correct 19 ms 2652 KB Output is correct
14 Correct 6 ms 1112 KB Output is correct
15 Correct 26 ms 2896 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 356 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 41 ms 4488 KB Output is correct
10 Correct 25 ms 3672 KB Output is correct
11 Correct 10 ms 1736 KB Output is correct
12 Correct 12 ms 1884 KB Output is correct
13 Correct 3 ms 600 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 34 ms 4632 KB Output is correct
10 Correct 34 ms 3828 KB Output is correct
11 Correct 10 ms 1628 KB Output is correct
12 Correct 12 ms 1880 KB Output is correct
13 Correct 3 ms 600 KB Output is correct
14 Correct 45 ms 5504 KB Output is correct
15 Correct 56 ms 6156 KB Output is correct
16 Correct 7 ms 1368 KB Output is correct
17 Correct 38 ms 4304 KB Output is correct
18 Correct 17 ms 2396 KB Output is correct