답안 #69714 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69714	2018-08-21T11:57:21 Z	MANcity	곤돌라 (IOI14_gondola)	C++14	75 / 100	28 ms	2480 KB

gondola

#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;
    //ANS=((LL)ANS*(LL)binpow(3,37))%Mod;
    //ANS=((LL)ANS*(LL)2)%Mod;
    //cout<<ANS<<endl;
    //cout<<V[0]<<" "<<V[1]<<" "<<V[2]<<" "<<V[3]<<" "<<V[4]<<" "<<V[5]<<endl;
    fo(i,1,l-1)
    {
        if(V[i]!=(V[i-1]+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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	3 ms	512 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	2 ms	512 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	4 ms	572 KB	Output is correct
4	Correct	3 ms	700 KB	Output is correct
5	Correct	4 ms	700 KB	Output is correct
6	Correct	12 ms	848 KB	Output is correct
7	Correct	17 ms	1228 KB	Output is correct
8	Correct	17 ms	1228 KB	Output is correct
9	Correct	10 ms	1228 KB	Output is correct
10	Correct	17 ms	1228 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1228 KB	Output is correct
2	Correct	3 ms	1228 KB	Output is correct
3	Correct	3 ms	1228 KB	Output is correct
4	Correct	3 ms	1228 KB	Output is correct
5	Correct	3 ms	1228 KB	Output is correct
6	Correct	13 ms	1228 KB	Output is correct
7	Correct	15 ms	1276 KB	Output is correct
8	Correct	13 ms	1276 KB	Output is correct
9	Correct	7 ms	1276 KB	Output is correct
10	Correct	12 ms	1280 KB	Output is correct
11	Correct	3 ms	1280 KB	Output is correct
12	Correct	2 ms	1280 KB	Output is correct
13	Correct	9 ms	1532 KB	Output is correct
14	Correct	3 ms	1532 KB	Output is correct
15	Correct	18 ms	1532 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1532 KB	Output is correct
2	Correct	2 ms	1532 KB	Output is correct
3	Correct	2 ms	1532 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	2 ms	1532 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1532 KB	Output is correct
2	Correct	3 ms	1532 KB	Output is correct
3	Correct	2 ms	1532 KB	Output is correct
4	Correct	2 ms	1532 KB	Output is correct
5	Correct	2 ms	1532 KB	Output is correct
6	Correct	2 ms	1532 KB	Output is correct
7	Correct	2 ms	1532 KB	Output is correct
8	Correct	2 ms	1532 KB	Output is correct
9	Correct	3 ms	1532 KB	Output is correct
10	Correct	2 ms	1532 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1532 KB	Output is correct
2	Correct	2 ms	1532 KB	Output is correct
3	Correct	3 ms	1532 KB	Output is correct
4	Correct	3 ms	1532 KB	Output is correct
5	Correct	3 ms	1532 KB	Output is correct
6	Correct	3 ms	1532 KB	Output is correct
7	Correct	3 ms	1532 KB	Output is correct
8	Correct	3 ms	1532 KB	Output is correct
9	Correct	3 ms	1532 KB	Output is correct
10	Correct	3 ms	1532 KB	Output is correct
11	Correct	20 ms	2100 KB	Output is correct
12	Correct	23 ms	2100 KB	Output is correct
13	Correct	18 ms	2100 KB	Output is correct
14	Correct	17 ms	2104 KB	Output is correct
15	Correct	28 ms	2480 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2480 KB	Output is correct
2	Correct	3 ms	2480 KB	Output is correct
3	Correct	3 ms	2480 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2480 KB	Output is correct
2	Correct	2 ms	2480 KB	Output is correct
3	Correct	2 ms	2480 KB	Output is correct
4	Correct	2 ms	2480 KB	Output is correct
5	Correct	3 ms	2480 KB	Output is correct
6	Correct	2 ms	2480 KB	Output is correct
7	Correct	3 ms	2480 KB	Output is correct
8	Correct	3 ms	2480 KB	Output is correct

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2480 KB	Output is correct
2	Correct	2 ms	2480 KB	Output is correct
3	Correct	2 ms	2480 KB	Output is correct
4	Correct	3 ms	2480 KB	Output is correct
5	Correct	3 ms	2480 KB	Output is correct
6	Correct	2 ms	2480 KB	Output is correct
7	Correct	2 ms	2480 KB	Output is correct
8	Correct	2 ms	2480 KB	Output is correct
9	Correct	21 ms	2480 KB	Output is correct
10	Correct	18 ms	2480 KB	Output is correct
11	Correct	9 ms	2480 KB	Output is correct
12	Correct	10 ms	2480 KB	Output is correct
13	Incorrect	5 ms	2480 KB	Output isn't correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2480 KB	Output is correct
2	Correct	3 ms	2480 KB	Output is correct
3	Correct	2 ms	2480 KB	Output is correct
4	Correct	3 ms	2480 KB	Output is correct
5	Correct	2 ms	2480 KB	Output is correct
6	Correct	3 ms	2480 KB	Output is correct
7	Correct	2 ms	2480 KB	Output is correct
8	Correct	2 ms	2480 KB	Output is correct
9	Correct	22 ms	2480 KB	Output is correct
10	Correct	26 ms	2480 KB	Output is correct
11	Correct	9 ms	2480 KB	Output is correct
12	Correct	10 ms	2480 KB	Output is correct
13	Incorrect	5 ms	2480 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #69714

Compilation message