oj.uz

Submission #65304

# Submission time Handle Problem Language Result Execution time Memory
65304 2018-08-07T10:41:00 Z gnoor Gondola (IOI14_gondola) C++17
90 / 100
 34 ms 2584 KB 
#include "gondola.h"

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

bool mark[300100];

int valid(int n, int inputSeq[])
{
	int key=-1;
	int id=-1;
	int cur;
	for (int i=0;i<n;i++) {
		inputSeq[i]--;
		if (mark[inputSeq[i]]) return 0;
		mark[inputSeq[i]]=true;
	}
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>=n) continue;
		key=inputSeq[i];
		id=i;
	}
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>=n) continue;
		cur=key+i-id;
		cur%=n;
		cur+=n;
		cur%=n;
		if (inputSeq[i]!=cur) return 0;
	}
	return 1;
}

//----------------------

int init[100100];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int id=0;
	int key=1;
	for (int i=0;i<n;i++) {
		if (gondolaSeq[i]>n) continue;
		id=i;
		key=gondolaSeq[i];
		break;
	}
	init[id]=key;
	for (int i=id+1;i<n;i++) {
		init[i]=init[i-1]+1;
		if (init[i]>n) init[i]-=n;
	}
	for (int i=id-1;i>=0;i--) {
		init[i]=init[i+1]-1;
		if (init[i]<=0) init[i]+=n;
	}

	vector<pair<int,int>> ei;
	for (int i=0;i<n;i++) {
		if (gondolaSeq[i]<=n) continue;
		ei.push_back({gondolaSeq[i],i});
	}
	sort(ei.begin(),ei.end());

	int sz=0;
	int curid=0;
	int curcar=n+1;
	int curgon=0;
	for (int i=0;i<(int)ei.size();i++) {
		while (curcar<ei[i].first) {
			while (init[curgon]==gondolaSeq[curgon]) curgon++;
			replacementSeq[sz++]=init[curgon];
			init[curgon]=curcar;
			curcar++;
		}
		replacementSeq[sz++]=init[ei[i].second];
		init[ei[i].second]=ei[i].first;
		curcar++;
	}
	return sz;
}

//----------------------
//
int mod=1000000009;

long long poww(long long b,int x) {
	if (x==0) return 1;
	if (x==1) return b;
	long long tmp=poww(b,x/2);
	tmp*=tmp;
	tmp%=mod;
	if (x%2) return (tmp*b)%mod;
	return tmp;
}

int countReplacement(int n, int inputSeq[])
{
	if (!valid(n,inputSeq)) return 0;
	for (int i=0;i<n;i++) inputSeq[i]++;
	int id=0;
	int key=1;
	for (int i=0;i<n;i++) {
		if (inputSeq[i]>n) continue;
		id=i;
		key=inputSeq[i];
		break;
	}
	init[id]=key;
	for (int i=id+1;i<n;i++) {
		init[i]=init[i-1]+1;
		if (init[i]>n) init[i]-=n;
	}
	for (int i=id-1;i>=0;i--) {
		init[i]=init[i+1]-1;
		if (init[i]<=0) init[i]+=n;
	}

	vector<pair<int,int>> ei;
	for (int i=0;i<n;i++) {
		if (inputSeq[i]<=n) continue;
		ei.push_back({inputSeq[i],i});
	}
	sort(ei.begin(),ei.end());
	int curcar=n+1;
	int cnt=ei.size();
	long long ans=1;
	if (cnt==n) ans=n;
	for (int i=0;i<(int)ei.size();i++) {
		ans*=poww(cnt,ei[i].first-curcar);
		ans%=mod;
		curcar=ei[i].first+1;
		cnt--;
	}
	return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:69:6: warning: unused variable 'curid' [-Wunused-variable]
  int curid=0;
      ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 504 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 8 ms 744 KB Output is correct
7 Correct 26 ms 948 KB Output is correct
8 Correct 16 ms 948 KB Output is correct
9 Correct 6 ms 948 KB Output is correct
10 Correct 16 ms 1000 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1000 KB Output is correct
2 Correct 3 ms 1000 KB Output is correct
3 Correct 2 ms 1000 KB Output is correct
4 Correct 3 ms 1000 KB Output is correct
5 Correct 2 ms 1000 KB Output is correct
6 Correct 7 ms 1000 KB Output is correct
7 Correct 16 ms 1080 KB Output is correct
8 Correct 14 ms 1080 KB Output is correct
9 Correct 8 ms 1080 KB Output is correct
10 Correct 14 ms 1080 KB Output is correct
11 Correct 2 ms 1080 KB Output is correct
12 Correct 3 ms 1080 KB Output is correct
13 Correct 8 ms 1080 KB Output is correct
14 Correct 3 ms 1080 KB Output is correct
15 Correct 18 ms 1080 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1080 KB Output is correct
2 Correct 2 ms 1080 KB Output is correct
3 Correct 2 ms 1080 KB Output is correct
4 Correct 3 ms 1080 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1080 KB Output is correct
2 Correct 4 ms 1080 KB Output is correct
3 Correct 3 ms 1080 KB Output is correct
4 Correct 2 ms 1080 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct
6 Correct 2 ms 1080 KB Output is correct
7 Correct 2 ms 1080 KB Output is correct
8 Correct 3 ms 1080 KB Output is correct
9 Correct 2 ms 1080 KB Output is correct
10 Correct 3 ms 1080 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1080 KB Output is correct
2 Correct 2 ms 1080 KB Output is correct
3 Correct 2 ms 1080 KB Output is correct
4 Correct 2 ms 1080 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct
6 Correct 3 ms 1080 KB Output is correct
7 Correct 2 ms 1080 KB Output is correct
8 Correct 3 ms 1080 KB Output is correct
9 Correct 3 ms 1080 KB Output is correct
10 Correct 3 ms 1080 KB Output is correct
11 Correct 14 ms 1180 KB Output is correct
12 Correct 17 ms 1308 KB Output is correct
13 Correct 21 ms 1696 KB Output is correct
14 Correct 14 ms 1696 KB Output is correct
15 Correct 34 ms 2584 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 3 ms 2584 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 3 ms 2584 KB Output is correct
3 Correct 3 ms 2584 KB Output is correct
4 Correct 3 ms 2584 KB Output is correct
5 Correct 3 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 2 ms 2584 KB Output is correct
8 Correct 3 ms 2584 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 3 ms 2584 KB Output is correct
4 Correct 3 ms 2584 KB Output is correct
5 Correct 2 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 2 ms 2584 KB Output is correct
8 Correct 4 ms 2584 KB Output is correct
9 Correct 32 ms 2584 KB Output is correct
10 Correct 23 ms 2584 KB Output is correct
11 Correct 12 ms 2584 KB Output is correct
12 Correct 12 ms 2584 KB Output is correct
13 Correct 6 ms 2584 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2584 KB Output is correct
2 Correct 3 ms 2584 KB Output is correct
3 Correct 3 ms 2584 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 3 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 3 ms 2584 KB Output is correct
8 Correct 3 ms 2584 KB Output is correct
9 Correct 26 ms 2584 KB Output is correct
10 Correct 25 ms 2584 KB Output is correct
11 Correct 10 ms 2584 KB Output is correct
12 Correct 15 ms 2584 KB Output is correct
13 Correct 4 ms 2584 KB Output is correct
14 Runtime error 20 ms 2584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -