답안 #8903 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8903	2014-09-23T21:51:46 Z	pichulia	곤돌라 (IOI14_gondola)	C++	90 / 100	24 ms	5972 KB

gondola

#include<stdio.h>
#include<algorithm>
using namespace std;
#include"gondola.h"
#define M 1000000009
int n;
int a[100009];
int b[100009];
int x[100009];
int xl;
int y[300009];
int nono;
long long int res = 1;
int resb[300009];
int rl;
bool not_gon()
{
    int i, j;
    for(i=0;i<n;i++)
    {
        x[xl++] = a[i];
        b[i] = i+1;
        y[a[i]]=i;
    }
    for(i=0;i<n;i++)
    {
        if(a[i]<=n)
            break;
    }
    sort(x,x+xl);
    xl = unique(x,x+xl)-x;
    if(xl<n) return true;
    if(i==n) return xl<n;
    nono = 1;
    for(j=0;j<n;j++)
    {
        int k = (i+j)%n;
        b[k] = (a[i] + j-1)%n+1;
        if(a[k] > n || a[k] == (a[i] + j-1)%n+1) continue;
        return true;
    }
    return false;
}
long long int poww(long long p, long long q)
{
	long long int x,z;
	x=1;z=p;
	while(q)
	{
		if(q%2){x = (x*z)%M;}
		z= (z*z)%M;
		q/=2;
	}
	return x;
}
void process()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	save = n - i;
	last = n;
	for(;i<xl;i++)
	{
		res = (res * poww(save,x[i] - last - 1))%M;
		save--;
		last = x[i];
	}
}
void process2()
{
	int i, j, k;
	int save = n;
	int last;
	for(i=0;i<xl;i++)
		if(x[i] > n)
			break;
	rl = 0;
	last = n;
	for(;i<xl;i++)
	{
		resb[rl++] = b[y[x[i]]];
		for(j=last+1;j<x[i];j++)
		{
			resb[rl++] = j;
		}
		last = x[i];
	}
}
int valid(int _n,int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = inputSeq[i];
	if(not_gon())
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int countReplacement(int _n, int inputSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
	{
		a[i] = inputSeq[i];
	}
  nono = 0;
	if(not_gon())
	{
		return 0;
	}
	else
	{
      res=1;
		if(nono==0)
		res = n;
		process();
		return res;
	}
}
int replacement(int _n, int gondolaSeq[], int replacementSeq[])
{
	int i, j, k;
	n = _n;
	for(i=0;i<n;i++)
		a[i] = gondolaSeq[i];
  if(not_gon())
    return 0;
	process2();
	resb[rl] = 0;
	for(i=0;i<rl;i++)
		replacementSeq[i] = resb[i];
  return rl;

}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	5972 KB	Output is correct
2	Correct	0 ms	5972 KB	Output is correct
3	Correct	0 ms	5972 KB	Output is correct
4	Correct	0 ms	5972 KB	Output is correct
5	Correct	0 ms	5972 KB	Output is correct
6	Correct	0 ms	5972 KB	Output is correct
7	Correct	0 ms	5972 KB	Output is correct
8	Correct	0 ms	5972 KB	Output is correct
9	Correct	16 ms	5972 KB	Output is correct
10	Correct	12 ms	5972 KB	Output is correct
11	Correct	4 ms	5972 KB	Output is correct
12	Correct	8 ms	5972 KB	Output is correct
13	Correct	0 ms	5972 KB	Output is correct
14	Runtime error	16 ms	5968 KB	SIGSEGV Segmentation fault
15	Halted	0 ms	0 KB	-

답안 #8903

Compilation message