답안 #70334 :: oj.uz

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

gondola

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

const int N=100006;
typedef long long ll;
const ll MOD=1000000007;
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	248 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	2 ms	484 KB	Output is correct
4	Correct	4 ms	484 KB	Output is correct
5	Correct	3 ms	516 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	516 KB	Output is correct
2	Correct	2 ms	516 KB	Output is correct
3	Correct	2 ms	516 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	22 ms	2512 KB	Output is correct
7	Correct	16 ms	2512 KB	Output is correct
8	Correct	39 ms	4200 KB	Output is correct
9	Correct	15 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	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	2 ms	4844 KB	Output is correct
5	Correct	2 ms	4844 KB	Output is correct
6	Correct	20 ms	4844 KB	Output is correct
7	Correct	15 ms	4844 KB	Output is correct
8	Correct	42 ms	4844 KB	Output is correct
9	Correct	18 ms	4844 KB	Output is correct
10	Correct	56 ms	4860 KB	Output is correct
11	Correct	4 ms	4860 KB	Output is correct
12	Correct	2 ms	4860 KB	Output is correct
13	Correct	9 ms	4860 KB	Output is correct
14	Correct	3 ms	4860 KB	Output is correct
15	Correct	21 ms	4860 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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

답안 #70334

Compilation message