oj.uz

Submission #70338

# Submission time Handle Problem Language Result Execution time Memory
70338 2018-08-22T16:04:37 Z Abelyan Gondola (IOI14_gondola) C++17
100 / 100
 125 ms 10396 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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