답안 #18703 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18703	2016-02-14T07:08:43 Z	suhgyuho_william	곤돌라 (IOI14_gondola)	C++	100 / 100	83 ms	8112 KB

gondola

#include "gondola.h"
#include <algorithm>
#include <map>

using namespace std;

map<int,bool> Map;
int valid(int n, int inputSeq[])
{
	int i;
	int s,t;

	s = -1;
    for(i=0; i<n; i++){
		if(Map.find(inputSeq[i]) != Map.end()) return 0;
		Map[inputSeq[i]] = true;
        if(inputSeq[i] <= n){
            t = i+2-inputSeq[i];
			if(t <= 0) t += n;
			if(s == -1){
				s = t;
			}else if(s != t){
				return 0;
			}
        }
    }
    return 1;
}

//----------------------
struct datar{
	int num,value;
}a[100002];
bool cmp(datar x,datar y){
	return x.value < y.value;
}
int first[100002];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int i,j,cnt;
	int s,t,big,nnum;

	s = -1;
    for(i=0; i<n; i++){
        if(gondolaSeq[i] <= n){
            t = i+2-gondolaSeq[i];
			if(t <= 0) t += n;
			s = t;
			break;
        }
    }
	big = 0;
	for(i=0; i<n; i++) big = max(big,gondolaSeq[i]);
    if(big == n){
		return 0;
    }
    for(i=n; i>=1; i--) gondolaSeq[i] = gondolaSeq[i-1];
    cnt = 0;
    if(s == -1) s = 1;
    first[s] = 1;
    for(i=1; i<n; i++){
		t = s+i;
		if(t > n) t -= n;
		first[t] = i+1;
    }
    for(i=1; i<=n; i++){
		a[i].num = i;
		a[i].value = gondolaSeq[i];
    }
    sort(a+1,a+n+1,cmp);
    nnum = n+1;
    if(a[1].value > n){
		replacementSeq[cnt] = first[a[1].num];
		cnt++; nnum++;
		for(i=nnum; i<=a[1].value; i++){
			replacementSeq[cnt] = nnum-1;
			cnt++; nnum++;
		}
    }
    for(i=2; i<=n; i++){
        if(a[i].value <= n) continue;
        replacementSeq[cnt] = first[a[i].num]; cnt++; nnum++;
        for(j=nnum; j<=a[i].value; j++){
			replacementSeq[cnt] = nnum-1;
			cnt++; nnum++;
        }
    }

	return cnt;
}

//----------------------
#define MOD 1000000009;

long long mul(long long x,long long y){ // return x^y;
	if(y == 0) return 1;
	if(y == 1) return x;
	long long tmp = mul(x,y/2);
	tmp *= tmp; tmp %= MOD;
	if(y%2 == 1){
		tmp *= x;
		tmp %= MOD;
	}
	return tmp;
}

long long ans;
int countReplacement(int n, int inputSeq[])
{
	if(valid(n,inputSeq) == 0) return 0;
	int i,j,t;
	int s,big;
	long long x,nnum;

	s = -1;
    for(i=0; i<n; i++){
        if(inputSeq[i] <= n){
            s = i+2-inputSeq[i];
			if(s <= 0) s += n;
			break;
        }
    }
	big = 0;
	for(i=0; i<n; i++) big = max(big,inputSeq[i]);
    if(big == n){
		return 1;
    }
    if(s == -1){
        s = 1;
		ans = (long long)n;
    }else ans = 1;

	for(i=n; i>=1; i--) inputSeq[i] = inputSeq[i-1];
    first[s] = 1;
    for(i=1; i<n; i++){
		t = s+i;
		if(t > n) t -= n;
		first[t] = i+1;
    }
    for(i=1; i<=n; i++){
		a[i].num = i;
		a[i].value = inputSeq[i];
    }
    sort(a+1,a+n+1,cmp);
    nnum = n+1;
    x = (long long)n;
    if(a[1].value > n){
		nnum++;
		ans *= mul(x,(long long)(a[1].value-nnum+1));
		ans %= MOD;
		nnum = a[1].value+1;
    }
    x--;
    for(i=2; i<=n; i++){
        if(a[i].value <= n){
			x--;
			continue;
        }
        nnum++;
        ans *= mul(x,(long long)(a[i].value-nnum+1));
        ans %= MOD;
        nnum = a[i].value+1;
        x--;
    }

	return (int)ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3756 KB	Output is correct
2	Correct	0 ms	3756 KB	Output is correct
3	Correct	0 ms	3756 KB	Output is correct
4	Correct	0 ms	3756 KB	Output is correct
5	Correct	0 ms	3756 KB	Output is correct
6	Correct	17 ms	5472 KB	Output is correct
7	Correct	0 ms	3756 KB	Output is correct
8	Correct	27 ms	7056 KB	Output is correct
9	Correct	5 ms	4812 KB	Output is correct
10	Correct	38 ms	7584 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3756 KB	Output is correct
2	Correct	0 ms	3756 KB	Output is correct
3	Correct	0 ms	3756 KB	Output is correct
4	Correct	0 ms	3756 KB	Output is correct
5	Correct	0 ms	3756 KB	Output is correct
6	Correct	18 ms	5472 KB	Output is correct
7	Correct	14 ms	3756 KB	Output is correct
8	Correct	31 ms	7056 KB	Output is correct
9	Correct	6 ms	4812 KB	Output is correct
10	Correct	38 ms	7584 KB	Output is correct
11	Correct	0 ms	3756 KB	Output is correct
12	Correct	0 ms	3756 KB	Output is correct
13	Correct	0 ms	3756 KB	Output is correct
14	Correct	0 ms	3756 KB	Output is correct
15	Correct	12 ms	3756 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3756 KB	Output is correct
2	Correct	0 ms	3756 KB	Output is correct
3	Correct	0 ms	3756 KB	Output is correct
4	Correct	0 ms	3756 KB	Output is correct
5	Correct	0 ms	3756 KB	Output is correct
6	Correct	0 ms	3756 KB	Output is correct
7	Correct	0 ms	3756 KB	Output is correct
8	Correct	0 ms	3756 KB	Output is correct
9	Correct	61 ms	7188 KB	Output is correct
10	Correct	44 ms	6528 KB	Output is correct
11	Correct	16 ms	4680 KB	Output is correct
12	Correct	19 ms	4944 KB	Output is correct
13	Correct	3 ms	4020 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3756 KB	Output is correct
2	Correct	0 ms	3756 KB	Output is correct
3	Correct	0 ms	3756 KB	Output is correct
4	Correct	0 ms	3756 KB	Output is correct
5	Correct	0 ms	3756 KB	Output is correct
6	Correct	0 ms	3756 KB	Output is correct
7	Correct	0 ms	3756 KB	Output is correct
8	Correct	0 ms	3756 KB	Output is correct
9	Correct	54 ms	7188 KB	Output is correct
10	Correct	38 ms	6528 KB	Output is correct
11	Correct	11 ms	4680 KB	Output is correct
12	Correct	20 ms	4944 KB	Output is correct
13	Correct	4 ms	4020 KB	Output is correct
14	Correct	73 ms	7584 KB	Output is correct
15	Correct	83 ms	8112 KB	Output is correct
16	Correct	9 ms	4548 KB	Output is correct
17	Correct	52 ms	6660 KB	Output is correct
18	Correct	28 ms	5340 KB	Output is correct

답안 #18703

Compilation message