oj.uz

Submission #69723

# Submission time Handle Problem Language Result Execution time Memory
69723 2018-08-21T12:04:49 Z MANcity Gondola (IOI14_gondola) C++14
75 / 100
 30 ms 5208 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;
int num[250012];
int valid(int n, int inputSeq[])
{
    for0(i,n-1)
        num[inputSeq[i]]++;
    for1(i,250002)
        if(num[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<int> 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-1);
    V.push_back(-1);
    sort(V.begin(),V.end());
    int l=V.size();
    LL ANS= 1;
    fo(i,1,l-1)
    {
        LL B=binpow((LL)(l-i),(LL)(V[i]-V[i-1]-1))%Mod;
        ANS=((LL)ANS*(LL)B)%Mod;
    }
    return ANS;
}
/*
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 380 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 608 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 660 KB Output is correct
6 Correct 10 ms 1108 KB Output is correct
7 Correct 15 ms 2016 KB Output is correct
8 Correct 13 ms 2268 KB Output is correct
9 Correct 6 ms 2268 KB Output is correct
10 Correct 13 ms 2460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2460 KB Output is correct
2 Correct 3 ms 2460 KB Output is correct
3 Correct 4 ms 2460 KB Output is correct
4 Correct 3 ms 2460 KB Output is correct
5 Correct 3 ms 2460 KB Output is correct
6 Correct 12 ms 2460 KB Output is correct
7 Correct 19 ms 2532 KB Output is correct
8 Correct 11 ms 2532 KB Output is correct
9 Correct 7 ms 2532 KB Output is correct
10 Correct 14 ms 2532 KB Output is correct
11 Correct 2 ms 2532 KB Output is correct
12 Correct 2 ms 2532 KB Output is correct
13 Correct 8 ms 2788 KB Output is correct
14 Correct 2 ms 2788 KB Output is correct
15 Correct 16 ms 2788 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2788 KB Output is correct
2 Correct 2 ms 2788 KB Output is correct
3 Correct 2 ms 2788 KB Output is correct
4 Correct 3 ms 2788 KB Output is correct
5 Correct 3 ms 2788 KB Output is correct
6 Correct 2 ms 2788 KB Output is correct
7 Correct 3 ms 2788 KB Output is correct
8 Correct 4 ms 2788 KB Output is correct
9 Correct 2 ms 2788 KB Output is correct
10 Correct 3 ms 2788 KB Output is correct
11 Correct 19 ms 3916 KB Output is correct
12 Correct 21 ms 4368 KB Output is correct
13 Correct 19 ms 4368 KB Output is correct
14 Correct 16 ms 4708 KB Output is correct
15 Correct 26 ms 5208 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5208 KB Output is correct
3 Correct 3 ms 5208 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 2 ms 5208 KB Output is correct
6 Correct 2 ms 5208 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 30 ms 5208 KB Output is correct
10 Correct 18 ms 5208 KB Output is correct
11 Correct 11 ms 5208 KB Output is correct
12 Correct 12 ms 5208 KB Output is correct
13 Incorrect 5 ms 5208 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 3 ms 5208 KB Output is correct
3 Correct 4 ms 5208 KB Output is correct
4 Correct 3 ms 5208 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 4 ms 5208 KB Output is correct
7 Correct 3 ms 5208 KB Output is correct
8 Correct 3 ms 5208 KB Output is correct
9 Correct 22 ms 5208 KB Output is correct
10 Correct 20 ms 5208 KB Output is correct
11 Correct 9 ms 5208 KB Output is correct
12 Correct 13 ms 5208 KB Output is correct
13 Incorrect 5 ms 5208 KB Output isn't correct
14 Halted 0 ms 0 KB -