답안 #69690 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69690	2018-08-21T11:44:39 Z	MANcity	곤돌라 (IOI14_gondola)	C++14	60 / 100	27 ms	2580 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+7;
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*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=(ANS+binpow(3,13))%Mod;
    //ANS=(ANS+binpow(2,6))%Mod;
    fo(i,1,l-1)
    {
        if(V[i]!=(V[i-1]+1))
        {
            ANS=((LL)ANS*binpow(l-i,V[i]-V[i-1]-1)%Mod)%Mod;
        }
    }
    return ANS;
}
/*
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	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	400 KB	Output is correct
4	Correct	3 ms	400 KB	Output is correct
5	Correct	3 ms	608 KB	Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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	2 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	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	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	3 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	3 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	2 ms	1532 KB	Output is correct
5	Correct	2 ms	1532 KB	Output is correct
6	Correct	3 ms	1532 KB	Output is correct
7	Correct	2 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	2 ms	1532 KB	Output is correct
11	Correct	16 ms	2068 KB	Output is correct
12	Correct	20 ms	2196 KB	Output is correct
13	Correct	19 ms	2196 KB	Output is correct
14	Correct	15 ms	2196 KB	Output is correct
15	Correct	27 ms	2580 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2580 KB	Output is correct
2	Correct	4 ms	2580 KB	Output is correct
3	Correct	2 ms	2580 KB	Output is correct
4	Correct	3 ms	2580 KB	Output is correct
5	Correct	3 ms	2580 KB	Output is correct
6	Correct	3 ms	2580 KB	Output is correct
7	Incorrect	3 ms	2580 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2580 KB	Output is correct
2	Correct	2 ms	2580 KB	Output is correct
3	Correct	2 ms	2580 KB	Output is correct
4	Correct	3 ms	2580 KB	Output is correct
5	Correct	2 ms	2580 KB	Output is correct
6	Correct	4 ms	2580 KB	Output is correct
7	Incorrect	5 ms	2580 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2580 KB	Output is correct
2	Correct	2 ms	2580 KB	Output is correct
3	Correct	3 ms	2580 KB	Output is correct
4	Correct	3 ms	2580 KB	Output is correct
5	Correct	3 ms	2580 KB	Output is correct
6	Correct	3 ms	2580 KB	Output is correct
7	Incorrect	3 ms	2580 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

답안 #69690

Compilation message