답안 #70328 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70328	2018-08-22T15:43:06 Z	Abelyan	곤돌라 (IOI14_gondola)	C++17	60 / 100	31 ms	8516 KB

gondola

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

const int N=100006;
typedef long long ll;
const ll MOD=1000000007;
bool used[N];

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	4 ms	388 KB	Output is correct
2	Correct	3 ms	492 KB	Output is correct
3	Correct	2 ms	624 KB	Output is correct
4	Correct	2 ms	624 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	624 KB	Output is correct
2	Correct	3 ms	692 KB	Output is correct
3	Correct	4 ms	692 KB	Output is correct
4	Correct	3 ms	692 KB	Output is correct
5	Correct	3 ms	692 KB	Output is correct
6	Correct	10 ms	1016 KB	Output is correct
7	Correct	20 ms	1612 KB	Output is correct
8	Correct	18 ms	1988 KB	Output is correct
9	Correct	7 ms	1988 KB	Output is correct
10	Correct	15 ms	2652 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2652 KB	Output is correct
2	Correct	2 ms	2652 KB	Output is correct
3	Correct	3 ms	2652 KB	Output is correct
4	Correct	3 ms	2652 KB	Output is correct
5	Correct	3 ms	2652 KB	Output is correct
6	Correct	10 ms	2780 KB	Output is correct
7	Correct	27 ms	3376 KB	Output is correct
8	Correct	15 ms	3752 KB	Output is correct
9	Correct	7 ms	3752 KB	Output is correct
10	Correct	18 ms	4564 KB	Output is correct
11	Correct	3 ms	4564 KB	Output is correct
12	Correct	4 ms	4564 KB	Output is correct
13	Correct	9 ms	4632 KB	Output is correct
14	Correct	2 ms	4632 KB	Output is correct
15	Correct	18 ms	5152 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5152 KB	Output is correct
2	Correct	2 ms	5152 KB	Output is correct
3	Correct	2 ms	5152 KB	Output is correct
4	Correct	3 ms	5152 KB	Output is correct
5	Correct	2 ms	5152 KB	Output is correct
6	Correct	3 ms	5152 KB	Output is correct
7	Correct	4 ms	5152 KB	Output is correct
8	Correct	3 ms	5152 KB	Output is correct
9	Correct	3 ms	5152 KB	Output is correct
10	Correct	3 ms	5152 KB	Output is correct
11	Correct	23 ms	6912 KB	Output is correct
12	Correct	23 ms	7368 KB	Output is correct
13	Correct	27 ms	7368 KB	Output is correct
14	Correct	20 ms	7956 KB	Output is correct
15	Correct	31 ms	8516 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	8516 KB	Output is correct
2	Correct	2 ms	8516 KB	Output is correct
3	Correct	2 ms	8516 KB	Output is correct
4	Correct	4 ms	8516 KB	Output is correct
5	Correct	2 ms	8516 KB	Output is correct
6	Correct	2 ms	8516 KB	Output is correct
7	Incorrect	3 ms	8516 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8516 KB	Output is correct
2	Correct	2 ms	8516 KB	Output is correct
3	Correct	3 ms	8516 KB	Output is correct
4	Correct	3 ms	8516 KB	Output is correct
5	Correct	2 ms	8516 KB	Output is correct
6	Correct	5 ms	8516 KB	Output is correct
7	Incorrect	2 ms	8516 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	8516 KB	Output is correct
2	Correct	3 ms	8516 KB	Output is correct
3	Correct	2 ms	8516 KB	Output is correct
4	Correct	3 ms	8516 KB	Output is correct
5	Correct	3 ms	8516 KB	Output is correct
6	Correct	2 ms	8516 KB	Output is correct
7	Incorrect	3 ms	8516 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

답안 #70328

Compilation message