oj.uz

Submission #69754

# Submission time Handle Problem Language Result Execution time Memory
69754 2018-08-21T12:45:37 Z MANcity Gondola (IOI14_gondola) C++14
100 / 100
 137 ms 9416 KB 
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
#include "gondola.h"
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+9;
map<int,int> mymap;
int valid(int n, int inputSeq[])
{
    for0(i,n-1)
        mymap[inputSeq[i]]++;
    for0(i,n-1)
        if(mymap[inputSeq[i]]>=2)
            return 0;
    for0(i,n-1)
    {
        if(inputSeq[i]<=n)
        {
            int N=inputSeq[i];
            fo(j,i+1,n-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]<=n && inputSeq[j]!=N)
                    return 0;
            }
            fo(j,0,i-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]<=n && inputSeq[j]!=N)
                    return 0;
            }
            return 1;
        }
    }
    return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    vector<pair<int,int> > V;
    int u=0;
    for0(i,n-1)
    {
        if(gondolaSeq[i]<=n)
        {
            u=1;
            int N=gondolaSeq[i];
            fo(j,i+1,n-1)
            {
                N++;
                if(N>n)
                    N-=n;
                V.push_back(mp(gondolaSeq[j],N));
            }
            fo(j,0,i-1)
            {
                N++;
                if(N>n)
                    N-=n;
                V.push_back(mp(gondolaSeq[j],N));
            }
            break;
        }
    }
    if(u==0)
        for0(i,n-1)
            V.push_back(mp(gondolaSeq[i],i+1));
    int q=(n+1);
    int num=-1;
    sort(V.begin(),V.end());
    for0(i,V.size()-1)
    {
        if(V[i].first!=V[i].second)
        {
            int B=V[i].first;
            int A=V[i].second;
            while(A!=B)
            {
                num++;
                replacementSeq[num]=A;
                A=q;
                q++;
            }
        }
    }
    return (num+1);
}

//----------------------
LL binpow(LL x,LL n)
{
    if(n==0)
        return 1;
    if(n%2==0)
    {
        LL A=binpow(x,n/2)%Mod;
        return ((LL)A*(LL)A)%Mod;
    }
    else
    {
        LL A=binpow(x,n-1)%Mod;
        return ((LL)A*(LL)x)%Mod;
    }
}
int countReplacement(int n, int inputSeq[])
{
    int t=valid(n,inputSeq);
    if(t==0)
        return 0;
    int qan=0;
    for0(i,n-1)
        if(inputSeq[i]<=n)
            qan++;
    if(qan==n)
        return 1;
    vector<LL> V;
    int u=0;
    for0(i,n-1)
    {
        if(inputSeq[i]<=n)
        {
            u=1;
            int N=inputSeq[i];
            fo(j,i+1,n-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]!=N)
                {
                    V.push_back(inputSeq[j]-n-1);
                }
            }
            fo(j,0,i-1)
            {
                N++;
                if(N>n)
                    N-=n;
                if(inputSeq[j]!=N)
                    V.push_back(inputSeq[j]-n-1);
            }
            break;
        }
    }
    if(u==0)
    {
        for0(i,n-1)
            V.push_back(inputSeq[i]-n);
    }
    V.push_back(-1);
    sort(V.begin(),V.end());
    int l=V.size();
    LL ANS=1;
    fo(i,1,l-1)
    {
        LL B=binpow(l-i,V[i]-V[i-1]-1)%Mod;
        ANS=((LL)ANS*(LL)B)%Mod;
        ANS%=Mod;
    }
    return (ANS)%Mod;
}
/*
8
21
14 15 64 17 59 19 20 21 1 2 3 4 5 6 7 8 9 10 11 61 13


8
37
9 10 11 12 13 14 15 16 17 18 19 59 21 51 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 58 2 3 4 5 6 7 8
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 612 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 612 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 23 ms 2380 KB Output is correct
7 Correct 41 ms 3924 KB Output is correct
8 Correct 36 ms 4172 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 57 ms 5344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5344 KB Output is correct
2 Correct 3 ms 5344 KB Output is correct
3 Correct 3 ms 5344 KB Output is correct
4 Correct 3 ms 5344 KB Output is correct
5 Correct 2 ms 5344 KB Output is correct
6 Correct 25 ms 5344 KB Output is correct
7 Correct 46 ms 5344 KB Output is correct
8 Correct 53 ms 5816 KB Output is correct
9 Correct 13 ms 5816 KB Output is correct
10 Correct 51 ms 6988 KB Output is correct
11 Correct 3 ms 6988 KB Output is correct
12 Correct 3 ms 6988 KB Output is correct
13 Correct 30 ms 6988 KB Output is correct
14 Correct 2 ms 6988 KB Output is correct
15 Correct 87 ms 7344 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7344 KB Output is correct
2 Correct 3 ms 7344 KB Output is correct
3 Correct 2 ms 7344 KB Output is correct
4 Correct 2 ms 7344 KB Output is correct
5 Correct 2 ms 7344 KB Output is correct
6 Correct 2 ms 7344 KB Output is correct
7 Correct 3 ms 7344 KB Output is correct
8 Correct 3 ms 7344 KB Output is correct
9 Correct 3 ms 7344 KB Output is correct
10 Correct 4 ms 7344 KB Output is correct
11 Correct 32 ms 7344 KB Output is correct
12 Correct 20 ms 7344 KB Output is correct
13 Correct 25 ms 7344 KB Output is correct
14 Correct 24 ms 7344 KB Output is correct
15 Correct 29 ms 7344 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7344 KB Output is correct
2 Correct 3 ms 7344 KB Output is correct
3 Correct 2 ms 7344 KB Output is correct
4 Correct 2 ms 7344 KB Output is correct
5 Correct 3 ms 7344 KB Output is correct
6 Correct 2 ms 7344 KB Output is correct
7 Correct 2 ms 7344 KB Output is correct
8 Correct 2 ms 7344 KB Output is correct
9 Correct 82 ms 7752 KB Output is correct
10 Correct 71 ms 7752 KB Output is correct
11 Correct 23 ms 7752 KB Output is correct
12 Correct 29 ms 7752 KB Output is correct
13 Correct 7 ms 7752 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7752 KB Output is correct
2 Correct 2 ms 7752 KB Output is correct
3 Correct 2 ms 7752 KB Output is correct
4 Correct 2 ms 7752 KB Output is correct
5 Correct 2 ms 7752 KB Output is correct
6 Correct 2 ms 7752 KB Output is correct
7 Correct 2 ms 7752 KB Output is correct
8 Correct 2 ms 7752 KB Output is correct
9 Correct 104 ms 7880 KB Output is correct
10 Correct 62 ms 7880 KB Output is correct
11 Correct 29 ms 7880 KB Output is correct
12 Correct 36 ms 7880 KB Output is correct
13 Correct 7 ms 7880 KB Output is correct
14 Correct 115 ms 8924 KB Output is correct
15 Correct 137 ms 9416 KB Output is correct
16 Correct 19 ms 9416 KB Output is correct
17 Correct 74 ms 9416 KB Output is correct
18 Correct 53 ms 9416 KB Output is correct