답안 #69696 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69696	2018-08-21T11:46:25 Z	MANcity	곤돌라 (IOI14_gondola)	C++14	60 / 100	27 ms	2568 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))
        {
            LL B=binpow((LL)(l-1),(LL)(V[i]-V[i-1]-1))%Mod;
            ANS=((LL)ANS*(LL)B)%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	4 ms	376 KB	Output is correct
2	Correct	4 ms	464 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	3 ms	504 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	564 KB	Output is correct
2	Correct	2 ms	564 KB	Output is correct
3	Correct	2 ms	564 KB	Output is correct
4	Correct	3 ms	564 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	8 ms	824 KB	Output is correct
7	Correct	15 ms	1212 KB	Output is correct
8	Correct	13 ms	1212 KB	Output is correct
9	Correct	6 ms	1212 KB	Output is correct
10	Correct	27 ms	1228 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 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	8 ms	1228 KB	Output is correct
7	Correct	21 ms	1300 KB	Output is correct
8	Correct	14 ms	1300 KB	Output is correct
9	Correct	6 ms	1300 KB	Output is correct
10	Correct	16 ms	1300 KB	Output is correct
11	Correct	2 ms	1300 KB	Output is correct
12	Correct	3 ms	1300 KB	Output is correct
13	Correct	12 ms	1532 KB	Output is correct
14	Correct	2 ms	1532 KB	Output is correct
15	Correct	17 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	3 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	3 ms	1532 KB	Output is correct
9	Correct	4 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	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
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	2 ms	1532 KB	Output is correct
10	Correct	4 ms	1532 KB	Output is correct
11	Correct	18 ms	2068 KB	Output is correct
12	Correct	19 ms	2200 KB	Output is correct
13	Correct	24 ms	2200 KB	Output is correct
14	Correct	15 ms	2200 KB	Output is correct
15	Correct	25 ms	2568 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #69696

Compilation message