답안 #69674 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69674	2018-08-21T11:29:57 Z	MANcity	곤돌라 (IOI14_gondola)	C++14	60 / 100	31 ms	2600 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=0;
    fo(i,1,l-1)
    {
        if(V[i]==(V[i-1]+1))
        {
            if(i==(l-1))
                ANS=(ANS+1)%Mod;
        }
        if(V[i]!=(V[i-1]+1))
        {
            ANS=(ANS+binpow(l-i,V[i]-V[i-1]-1)%Mod)%Mod;
        }
    }
    return ANS;
}
/*
8 2
3 4
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	584 KB	Output is correct
2	Correct	2 ms	592 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	2 ms	620 KB	Output is correct
5	Correct	2 ms	636 KB	Output is correct
6	Correct	7 ms	892 KB	Output is correct
7	Correct	17 ms	1276 KB	Output is correct
8	Correct	19 ms	1276 KB	Output is correct
9	Correct	6 ms	1276 KB	Output is correct
10	Correct	16 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	2 ms	1276 KB	Output is correct
3	Correct	2 ms	1276 KB	Output is correct
4	Correct	3 ms	1276 KB	Output is correct
5	Correct	2 ms	1276 KB	Output is correct
6	Correct	8 ms	1276 KB	Output is correct
7	Correct	18 ms	1276 KB	Output is correct
8	Correct	16 ms	1276 KB	Output is correct
9	Correct	5 ms	1276 KB	Output is correct
10	Correct	15 ms	1276 KB	Output is correct
11	Correct	2 ms	1276 KB	Output is correct
12	Correct	3 ms	1276 KB	Output is correct
13	Correct	10 ms	1532 KB	Output is correct
14	Correct	3 ms	1532 KB	Output is correct
15	Correct	26 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	3 ms	1532 KB	Output is correct
3	Correct	3 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	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	4 ms	1532 KB	Output is correct
9	Correct	5 ms	1532 KB	Output is correct
10	Correct	3 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	3 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	3 ms	1532 KB	Output is correct
8	Correct	4 ms	1532 KB	Output is correct
9	Correct	4 ms	1532 KB	Output is correct
10	Correct	3 ms	1532 KB	Output is correct
11	Correct	28 ms	2084 KB	Output is correct
12	Correct	22 ms	2144 KB	Output is correct
13	Correct	22 ms	2144 KB	Output is correct
14	Correct	19 ms	2144 KB	Output is correct
15	Correct	31 ms	2600 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #69674

Compilation message