Submission #287912

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
287912	2020-09-01T06:32:59 Z	shrek12357	Gondola (IOI14_gondola)	C++14	60 / 100	45 ms	4984 KB

gondola

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <fstream>
#include <queue>
#include "gondola.h"
using namespace std;

#define MOD 1000000009

int valid(int n, int inputSeq[]) {
	set<int> found;
	for (int i = 0; i < n; i++) {
		found.insert(inputSeq[i]);
	}
	if (found.size() != n) {
		return 0;
	}
	int idx = -1;
	int val = 0;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] <= n) {
			idx = i;
			val = inputSeq[i];
			break;
		}
	}
	if (idx == -1) {
		return 1;
	}
	int actual[100005];
	actual[idx] = val;
	val++;
	if (val > n) {
		val -= n;
	}
	for (int i = 1; i < n; i++) {
		int cur = (idx + i + n) % n;
		int pre = (idx + i - 1 + n) % n;
		actual[cur] = val;
		val++;
		if (val > n) {
			val -= n;
		}
	}
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] <= n && inputSeq[i] != actual[i]) {
			return 0;
		}
	}
	return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int idx = -1, val = 0;
	for (int i = 0; i < n; i++) {
		if (gondolaSeq[i] <= n) {
			idx = i;
			val = gondolaSeq[i];
			break;
		}
	}
	if (idx == -1) {
		idx = 0;
		val = 1;
	}
	int actual[100005];
	actual[idx] = val;
	val++;
	if (val > n) {
		val -= n;
	}
	for (int i = 1; i < n; i++) {
		int cur = (idx + i + n) % n;
		int pre = (idx + i - 1 + n) % n;
		actual[cur] = val;
		val++;
		if (val > n) {
			val -= n;
		}
	}
	set<pair<int, int>> changes;
	for (int i = 0; i < n; i++) {
		if (gondolaSeq[i] > n) {
			changes.insert({ gondolaSeq[i], actual[i]});
		}
	}
	int cur = n + 1;
	vector<int> ans;
	while (changes.size() > 0) {
		if (cur == changes.begin()->first) {
			ans.push_back(changes.begin()->second);
			changes.erase(changes.begin());
		}
		else {
			ans.push_back(changes.begin()->second);
			int temp = changes.begin()->first;
			changes.erase(changes.begin());
			changes.insert({ temp, cur });
		}
		cur++;
	}
	for (int i = 0; i < ans.size(); i++) {
		replacementSeq[i] = ans[i];
		//cout << replacementSeq[i] << endl;
		if (ans[i] == 0) {
			return 5000;
			break;
		}
	}
	return ans.size();
}

int countReplacement(int n, int inputSeq[]) {
	if (!valid(n, inputSeq)) {
		return 0;
	}
	int counter = 0;
	set<int> nums;
	int cur = n + 1;
	for (int i = 0; i < n; i++) {
		if (inputSeq[i] > n) {
			counter++;
			nums.insert(inputSeq[i]);
		}
	}
	if (counter == 0) {
		return 1;
	}
	long long ans = 1;
	while (nums.size() > 0) {
		ans = (ans*(long long)(pow(counter, *nums.begin() - cur)) % MOD) % MOD;
		counter--;
		cur = *nums.begin();
		nums.erase(nums.begin());
	}
	return (int)ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:21:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |  if (found.size() != n) {
      |      ~~~~~~~~~~~~~^~~~
gondola.cpp:44:7: warning: unused variable 'pre' [-Wunused-variable]
   44 |   int pre = (idx + i - 1 + n) % n;
      |       ^~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:80:7: warning: unused variable 'pre' [-Wunused-variable]
   80 |   int pre = (idx + i - 1 + n) % n;
      |       ^~~
gondola.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for (int i = 0; i < ans.size(); i++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	13 ms	2344 KB	Output is correct
7	Correct	33 ms	3704 KB	Output is correct
8	Correct	26 ms	4224 KB	Output is correct
9	Correct	8 ms	1536 KB	Output is correct
10	Correct	30 ms	4856 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	13 ms	2432 KB	Output is correct
7	Correct	33 ms	3704 KB	Output is correct
8	Correct	29 ms	4216 KB	Output is correct
9	Correct	8 ms	1536 KB	Output is correct
10	Correct	29 ms	4856 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	1 ms	512 KB	Output is correct
13	Correct	17 ms	2304 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	45 ms	4984 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	256 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct
4	Correct	384 KB	Output is correct
5	Correct	384 KB	Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	256 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	512 KB	Output is correct
11	Correct	12 ms	896 KB	Output is correct
12	Correct	14 ms	1024 KB	Output is correct
13	Correct	28 ms	2916 KB	Output is correct
14	Correct	15 ms	896 KB	Output is correct
15	Correct	40 ms	3164 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Incorrect	0 ms	384 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Incorrect	1 ms	376 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Incorrect	1 ms	384 KB	Output isn't correct
6	Halted	0 ms	0 KB	-