oj.uz

Submission #70328

# Submission time Handle Problem Language Result Execution time Memory
70328 2018-08-22T15:43:06 Z Abelyan Gondola (IOI14_gondola) C++17
60 / 100
 31 ms 8516 KB 
#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

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

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

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

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

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

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

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

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

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

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