oj.uz

답안 #60528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60528 2018-07-24T10:03:37 Z hamzqq9 곤돌라 (IOI14_gondola) C++14
75 / 100
 75 ms 3628 KB 
#include "gondola.h"
#define st first
#define nd second
#define ii pair<int,int> 
#define pb push_back
#define sz(x) (x.size())
#include<bits/stdc++.h>
using namespace std;

int find_fixed(int n,int inputSeq[]) {

	int fixed=0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) {

			fixed=i;

			break ;

		}

	}

	return fixed;

}

int valid(int n, int inputSeq[]) {

	map<int,int> fr;

	int fixed=find_fixed(n,inputSeq);

	int tot=2,big=0;

	int cur=inputSeq[fixed];

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(inputSeq[i]>n) {
		
			fr[inputSeq[i]]++;

			big++;

			continue ;
		
		}

		if(inputSeq[i]!=cur) return 0;

	}

	for(auto x:fr) {

		if(x.nd>1) return 0;

	}

	return 1;

}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {

	int fixed=find_fixed(n,gondolaSeq);

	int cur=(gondolaSeq[fixed]<=n?gondolaSeq[fixed]:1);
	int tot=2;

	vector<ii> change;

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(gondolaSeq[i]>n) {

			change.pb({gondolaSeq[i],cur});

		}

	}

	sort(change.begin(),change.end());

	int sz=0;
	int val=n;

	for(int i=0;i<sz(change);i++) {

		auto x=change[i];

		replacementSeq[sz++]=x.nd;

		val++;

		while(val<x.st) {

			replacementSeq[sz++]=val++;

		}

	}

	return sz;

}
#define MOD 1000000009
//----------------------

int fe(int x,int y) {

	if(y==0) return 1;
	if(y==1) return x;

	int res=fe(x,y/2);

	res=1ll*res*res%MOD;

	if(y&1) return 1ll*res*x%MOD;

	return res;

}

int countReplacement(int n, int inputSeq[]) {

	int isvalid=valid(n,inputSeq);

	int ans=1;

	vector<int> ranges;

	if(!isvalid) return 0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) continue ;

		ranges.pb(inputSeq[i]);

	}

	ranges.pb(n);

	sort(ranges.begin(),ranges.end());

	int cursz=sz(ranges)-1;

	for(int i=1;i<sz(ranges);i++,cursz--) {

		int range=ranges[i]-ranges[i-1]-1;

		ans=1ll*ans*fe(cursz,range)%MOD;

	}

	return ans;

}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:96:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(change);i++) {
               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:157:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<sz(ranges);i++,cursz--) {
               ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 544 KB Output is correct
2 Correct 3 ms 544 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 9 ms 748 KB Output is correct
7 Correct 15 ms 876 KB Output is correct
8 Correct 18 ms 880 KB Output is correct
9 Correct 8 ms 880 KB Output is correct
10 Correct 15 ms 984 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2580 KB Output is correct
2 Correct 2 ms 2580 KB Output is correct
3 Correct 2 ms 2580 KB Output is correct
4 Correct 3 ms 2580 KB Output is correct
5 Correct 3 ms 2580 KB Output is correct
6 Correct 3 ms 2580 KB Output is correct
7 Correct 3 ms 2580 KB Output is correct
8 Correct 3 ms 2580 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2580 KB Output is correct
2 Correct 2 ms 2580 KB Output is correct
3 Correct 3 ms 2580 KB Output is correct
4 Correct 2 ms 2580 KB Output is correct
5 Correct 3 ms 2580 KB Output is correct
6 Correct 2 ms 2580 KB Output is correct
7 Correct 0 ms 2580 KB Output is correct
8 Correct 3 ms 2580 KB Output is correct
9 Correct 75 ms 3560 KB Output is correct
10 Correct 64 ms 3560 KB Output is correct
11 Correct 28 ms 3560 KB Output is correct
12 Correct 28 ms 3560 KB Output is correct
13 Incorrect 8 ms 3560 KB Output isn't correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3560 KB Output is correct
2 Correct 2 ms 3560 KB Output is correct
3 Correct 3 ms 3560 KB Output is correct
4 Correct 3 ms 3560 KB Output is correct
5 Correct 2 ms 3560 KB Output is correct
6 Correct 3 ms 3560 KB Output is correct
7 Correct 2 ms 3560 KB Output is correct
8 Correct 2 ms 3560 KB Output is correct
9 Correct 57 ms 3628 KB Output is correct
10 Correct 53 ms 3628 KB Output is correct
11 Correct 20 ms 3628 KB Output is correct
12 Correct 24 ms 3628 KB Output is correct
13 Incorrect 7 ms 3628 KB Output isn't correct
14 Halted 0 ms 0 KB -