답안 #70338 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70338	2018-08-22T16:04:37 Z	Abelyan	곤돌라 (IOI14_gondola)	C++17	100 / 100	125 ms	10396 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

const int N=100006;
typedef long long ll;
const ll MOD=1000000009;
map<int,bool> used;

ll pwr(int num,int power){
	if (power==0) return 1;
	if (power==1) return num;
	ll sqr=pwr(num,power/2);
	ll ans=sqr*sqr;
	ans%=MOD;
	if (power%2){
		ans*=num;
		ans%=MOD;
	}
	return ans;
}

int valid(int n, int inSeq[])
{
	int start=-1;
	for (int i=0;i<n;i++){
		if (used[inSeq[i]]){
			return 0;
		}
		used[inSeq[i]]=true;
		if (inSeq[i]<=n){
			if (start!=-1 && (n+i-inSeq[i]+1)%n!=start){
				return 0;
			}
			start=(n+i-inSeq[i]+1)%n;
		}
	}
	return 1;
}


int replacement(int n, int inSeq[], int finalAns[])
{
	//cout<<n<<endl;
	if (n==0) return 0;
	int start=0;
	for (int i=0;i<n;i++){
		if (inSeq[i]<=n){
			start=(n+i-inSeq[i]+1)%n;
		}
	}
	vector<pair<int,int> > v;
	for (int i=0;i<n;i++){
		v.push_back({inSeq[i],(n+i-start)%n+1});
	}
	sort(v.begin(),v.end());
	int ansLength=0;
	int curGondola=n+1;
	for (int i=0;i<n;i++){
		//cout<<i<<endl;
		if (v[i].second==v[i].first)continue;
		finalAns[ansLength++]=v[i].second;
		curGondola++;
		//cout<<v[i].first<<endl;
		while (curGondola!=v[i].first+1){
			//cout<<ansLength<<" ";
			finalAns[ansLength++]=curGondola-1;
			curGondola++;
		}
	}
	return ansLength;
}


int countReplacement(int n, int inSeq[])
{
	if (!valid(n,inSeq)) return 0;
	bool untilN=false;
	for (int i=0;i<n;i++){
		if (inSeq[i]<=n){
			untilN=true;
		}
	}
	vector<int> v;
	for (int i=0;i<n;i++){
		v.push_back(inSeq[i]);
	}
	sort(v.begin(),v.end());
	ll finalAns=1;
	int curGondola=n+1;
	for (int i=0;i<n;i++){
		if (v[i]<=n)continue;
		//cout<<finalAns<<endl;
		finalAns*=pwr(n-i,v[i]-curGondola);
		finalAns%=MOD;
		curGondola=v[i]+1;
	}
	if (!untilN){
		finalAns*=n;
		finalAns%=MOD;
	}
	return finalAns;
}
/*
int gondolaSequence[100001];
int replacementSequence[250001];

int main()
{
  //freopen("05-007.in","r",stdin);
  int i, n, tag;
  int nr; 
  assert(scanf("%d", &tag)==1);
  assert(scanf("%d", &n)==1);
  for(i=0;i< n;i++)
    assert( scanf("%d", &gondolaSequence[i]) ==1);
  
  switch (tag){
  case 1: case 2: case 3:
    printf("%d\n", valid(n, gondolaSequence));
    break;

  case 4: case 5: case 6:
    nr = replacement(n, gondolaSequence, replacementSequence);
    printf("%d ", nr);
    if (nr > 0)
      {
	for (i=0; i<nr-1; i++)
	  printf("%d ", replacementSequence[i]);
	printf("%d\n", replacementSequence[nr-1]);
      }  
    else printf("\n");
    break;

  case 7: case 8: case 9: case 10:
    printf("%d\n",  countReplacement(n, gondolaSequence));  
    break;
  }

  return 0;
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	544 KB	Output is correct
2	Correct	2 ms	592 KB	Output is correct
3	Correct	3 ms	592 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct
5	Correct	2 ms	612 KB	Output is correct
6	Correct	20 ms	2504 KB	Output is correct
7	Correct	18 ms	2504 KB	Output is correct
8	Correct	35 ms	4200 KB	Output is correct
9	Correct	13 ms	4200 KB	Output is correct
10	Correct	51 ms	4844 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4844 KB	Output is correct
2	Correct	2 ms	4844 KB	Output is correct
3	Correct	3 ms	4844 KB	Output is correct
4	Correct	3 ms	4844 KB	Output is correct
5	Correct	3 ms	4844 KB	Output is correct
6	Correct	3 ms	4844 KB	Output is correct
7	Correct	2 ms	4844 KB	Output is correct
8	Correct	2 ms	4844 KB	Output is correct
9	Correct	85 ms	5536 KB	Output is correct
10	Correct	69 ms	5536 KB	Output is correct
11	Correct	26 ms	5536 KB	Output is correct
12	Correct	25 ms	5536 KB	Output is correct
13	Correct	7 ms	5536 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5536 KB	Output is correct
2	Correct	2 ms	5536 KB	Output is correct
3	Correct	2 ms	5536 KB	Output is correct
4	Correct	2 ms	5536 KB	Output is correct
5	Correct	2 ms	5536 KB	Output is correct
6	Correct	2 ms	5536 KB	Output is correct
7	Correct	3 ms	5536 KB	Output is correct
8	Correct	3 ms	5536 KB	Output is correct
9	Correct	82 ms	6776 KB	Output is correct
10	Correct	72 ms	6776 KB	Output is correct
11	Correct	22 ms	6776 KB	Output is correct
12	Correct	25 ms	6776 KB	Output is correct
13	Correct	7 ms	6776 KB	Output is correct
14	Correct	109 ms	8884 KB	Output is correct
15	Correct	125 ms	10396 KB	Output is correct
16	Correct	16 ms	10396 KB	Output is correct
17	Correct	66 ms	10396 KB	Output is correct
18	Correct	40 ms	10396 KB	Output is correct

답안 #70338

Compilation message