답안 #69723 :: oj.uz

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #69723

Compilation message