답안 #69725 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69725	2018-08-21T12:06:21 Z	MANcity	곤돌라 (IOI14_gondola)	C++14	75 / 100	32 ms	2584 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;
    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;
        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

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	524 KB	Output is correct
2	Correct	2 ms	552 KB	Output is correct
3	Correct	3 ms	552 KB	Output is correct
4	Correct	4 ms	552 KB	Output is correct
5	Correct	3 ms	552 KB	Output is correct
6	Correct	8 ms	824 KB	Output is correct
7	Correct	15 ms	1304 KB	Output is correct
8	Correct	13 ms	1304 KB	Output is correct
9	Correct	6 ms	1304 KB	Output is correct
10	Correct	14 ms	1304 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1508 KB	Output is correct
2	Correct	3 ms	1508 KB	Output is correct
3	Correct	2 ms	1508 KB	Output is correct
4	Correct	2 ms	1508 KB	Output is correct
5	Correct	2 ms	1508 KB	Output is correct
6	Correct	2 ms	1508 KB	Output is correct
7	Correct	3 ms	1508 KB	Output is correct
8	Correct	4 ms	1508 KB	Output is correct
9	Correct	4 ms	1508 KB	Output is correct
10	Correct	3 ms	1508 KB	Output is correct
11	Correct	18 ms	2084 KB	Output is correct
12	Correct	28 ms	2156 KB	Output is correct
13	Correct	18 ms	2156 KB	Output is correct
14	Correct	17 ms	2156 KB	Output is correct
15	Correct	32 ms	2584 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #69725

Compilation message