답안 #7677 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
7677	2014-08-13T17:00:59 Z	dohyun0324	곤돌라 (IOI14_gondola)	C++	90 / 100	48 ms	10704 KB

gondola

#include "gondola.h"
#include<algorithm>
#include<map>
#include<string.h>
using namespace std;
map<int,int>visit2;
int a[100010],ch[250010],visit[250010];
struct data
{
    int x,y;
    bool operator<(const data&r)const
    {
        return x<r.x;
    }
}arr[250010];
int valid(int n, int inputSeq[])
{
    int i,k=0;
    for(i=0;i<n;i++)
    {
        if(visit[inputSeq[i]]==1) return 0;
        visit[inputSeq[i]]=1;
        if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
    }
    for(i=1;i<=n;i++)
    {
        if(ch[i]!=0 && k==0)
        {
            k=ch[i];
            continue;
        }
        if(k!=0)
        {
            k++;
            if(k>n) k=1;
        }
        if(ch[i]!=0 && k!=ch[i]) return 0;
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int s,i,big=0,k=1,w=0,top=0,pos=0,p=0;
    for(i=0;i<n;i++)
    {
        ch[gondolaSeq[i]]=1;
        if(gondolaSeq[i]<=n) visit[i]=1;
        if(big<gondolaSeq[i]) big=gondolaSeq[i];
        if(gondolaSeq[i]<=n) pos=i,p=gondolaSeq[i];
    }
    for(i=0;i<n;i++)
    {
        if(visit[i]==0)
        {
            top++;
            arr[top].x=gondolaSeq[i];
            arr[top].y=i;
        }
    }
    sort(arr+1,arr+top+1);
    if(p==0)
    {
        for(i=0;i<n;i++) a[i]=i+1;
    }
    else
    {
        for(i=pos;i<=pos+n-1;i++)
        {
            a[i%n]=p;
            p++;
            if(p==n+1) p=1;
        }
    }
    for(i=n+1;i<=big;i++)
    {
        if(ch[i]==0)
        {
            replacementSeq[w++]=a[arr[k].y];
            a[arr[k].y]=i;
        }
        else
        {
            replacementSeq[w++]=a[arr[k].y];
            a[arr[k].y]=i;
            k++;
        }
    }
    return w;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
    int s,i,big=0,k=0,w=0,top=0,pos=0,p=0;
    long long int dap=1,c;
    for(i=0;i<n;i++)
    {
        if(visit2[inputSeq[i]]==1) return 0;
        visit2[inputSeq[i]]=1;
        if(inputSeq[i]<=n) ch[inputSeq[i]]=i+1;
    }
    for(i=1;i<=n;i++)
    {
        if(ch[i]!=0 && k==0)
        {
            k=ch[i];
            continue;
        }
        if(k!=0)
        {
            k++;
            if(k>n) k=1;
        }
        if(ch[i]!=0 && k!=ch[i]) return 0;
    }
    k=1;
    memset(ch,0,sizeof ch);
    for(i=0;i<n;i++)
    {
        ch[inputSeq[i]]=1;
        if(inputSeq[i]<=n) visit[i]=1;
        if(big<inputSeq[i]) big=inputSeq[i];
        if(inputSeq[i]<=n) pos=i,p=inputSeq[i];
    }
    for(i=0;i<n;i++)
    {
        if(visit[i]==0)
        {
            top++;
            arr[top].x=inputSeq[i];
            arr[top].y=i;
        }
    }
    sort(arr+1,arr+top+1);
    if(p==0)
    {
        for(i=0;i<n;i++) a[i]=i+1;
        dap=n;
    }
    else
    {
        for(i=pos;i<=pos+n-1;i++)
        {
            a[i%n]=p;
            p++;
            if(p==n+1) p=1;
        }
    }
    c=top;
    for(i=n+1;i<=big;i++)
    {
        if(ch[i]==1)
        {
            c--;
            continue;
        }
        if(c>0) dap*=c;
        dap%=1000000009;
    }
    return dap;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6880 KB	Output is correct
2	Correct	6880 KB	Output is correct
3	Correct	6880 KB	Output is correct
4	Correct	6880 KB	Output is correct
5	Correct	6880 KB	Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6880 KB	Output is correct
2	Correct	6880 KB	Output is correct
3	Correct	6880 KB	Output is correct
4	Correct	6880 KB	Output is correct
5	Correct	6880 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	6880 KB	Output is correct
2	Correct	6880 KB	Output is correct
3	Correct	6880 KB	Output is correct
4	Correct	6880 KB	Output is correct
5	Correct	6880 KB	Output is correct
6	Correct	6880 KB	Output is correct
7	Correct	6880 KB	Output is correct
8	Correct	6880 KB	Output is correct
9	Correct	6880 KB	Output is correct
10	Correct	6880 KB	Output is correct

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	6880 KB	Output is correct
2	Correct	6880 KB	Output is correct
3	Correct	6880 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	메모리	Grader output
1	Correct	6880 KB	Output is correct
2	Correct	6880 KB	Output is correct
3	Correct	6880 KB	Output is correct
4	Correct	6880 KB	Output is correct
5	Correct	6880 KB	Output is correct
6	Correct	6880 KB	Output is correct
7	Correct	6880 KB	Output is correct
8	Correct	6880 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6880 KB	Output is correct
2	Correct	0 ms	6880 KB	Output is correct
3	Correct	0 ms	6880 KB	Output is correct
4	Correct	0 ms	6880 KB	Output is correct
5	Correct	0 ms	6880 KB	Output is correct
6	Correct	0 ms	6880 KB	Output is correct
7	Correct	0 ms	6880 KB	Output is correct
8	Correct	0 ms	6880 KB	Output is correct
9	Correct	44 ms	10312 KB	Output is correct
10	Correct	44 ms	9652 KB	Output is correct
11	Correct	12 ms	7804 KB	Output is correct
12	Correct	20 ms	8068 KB	Output is correct
13	Correct	0 ms	7144 KB	Output is correct

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	6880 KB	Output is correct
2	Correct	0 ms	6880 KB	Output is correct
3	Correct	0 ms	6880 KB	Output is correct
4	Correct	0 ms	6880 KB	Output is correct
5	Correct	0 ms	6880 KB	Output is correct
6	Correct	0 ms	6880 KB	Output is correct
7	Correct	0 ms	6880 KB	Output is correct
8	Correct	0 ms	6880 KB	Output is correct
9	Correct	48 ms	10312 KB	Output is correct
10	Correct	44 ms	9652 KB	Output is correct
11	Correct	16 ms	7804 KB	Output is correct
12	Correct	20 ms	8068 KB	Output is correct
13	Correct	4 ms	7144 KB	Output is correct
14	Runtime error	48 ms	10704 KB	Program hung waiting for input
15	Halted	0 ms	0 KB	-

답안 #7677

Compilation message