oj.uz

Submission #237160

# Submission time Handle Problem Language Result Execution time Memory
237160 2020-06-04T22:26:08 Z mode149256 Gondola (IOI14_gondola) C++14
55 / 100
 51 ms 5624 KB 
/*input

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

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;

vi kur(250002);

int valid(int n, int inputSeq[])
{
	set<int> turiu;
	for (int i = 0; i < n; ++i)
	{
		if(turiu.find(inputSeq[i]) != turiu.end()) return 0;
		turiu.insert(inputSeq[i]);
	}
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (inputSeq[i] <= n) {
			pos = (i - inputSeq[i] + 1 + n) % n;
			break;
		}
	}
	if (pos == -1) return 1;

	for (int i = 0; i < n; ++i)
	{
		if (inputSeq[(pos + i) % n] <= n and inputSeq[(pos + i) % n] != i + 1)
			return 0;
	}

	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{

	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (gondolaSeq[i] <= n) {
			pos = (i - gondolaSeq[i] + 1 + n) % n;
			break;
		}
	}

	vi inputSeq;
	if (pos == -1) {
		for (int i = 1; i <= n; ++i)
			inputSeq.emplace_back(i);
	} else {
		inputSeq.resize(n);
		for (int i = 0; i < n; ++i)
			inputSeq[(pos + i) % n] = i + 1;
	}

	vpi sk; // {val, pos}


	for (int i = 0; i < n; ++i)
	{
		if (gondolaSeq[i] > n) {
			sk.emplace_back(gondolaSeq[i], i);
		}
	}

	sort(sk.begin(), sk.end());

	int piv = n + 1;

	// for (auto u : sk) printf("%d %d\n", u.x, u.y);
	int ind = 0;
	for (int i = 0; i < (int)sk.size(); ++i)
	{
		while (inputSeq[sk[i].y] != gondolaSeq[sk[i].y]) {
			replacementSeq[ind++] = inputSeq[sk[i].y];
			// sk[i].x = piv++;
			inputSeq[sk[i].y] = piv++;
		}
	}

	return ind;
}

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

int countReplacement(int n, int inputSeq[])
{
	return -3;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1408 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 20 ms 3200 KB Output is correct
7 Correct 17 ms 1664 KB Output is correct
8 Correct 33 ms 4984 KB Output is correct
9 Correct 12 ms 2432 KB Output is correct
10 Correct 39 ms 5624 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 19 ms 3200 KB Output is correct
7 Correct 17 ms 1664 KB Output is correct
8 Correct 31 ms 4992 KB Output is correct
9 Correct 13 ms 2432 KB Output is correct
10 Correct 39 ms 5496 KB Output is correct
11 Correct 5 ms 1280 KB Output is correct
12 Correct 5 ms 1280 KB Output is correct
13 Correct 23 ms 3072 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 51 ms 5624 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 5 ms 1280 KB Output is correct
7 Correct 5 ms 1280 KB Output is correct
8 Correct 6 ms 1408 KB Output is correct
9 Correct 5 ms 1280 KB Output is correct
10 Correct 5 ms 1408 KB Output is correct
11 Correct 15 ms 1920 KB Output is correct
12 Correct 17 ms 2048 KB Output is correct
13 Correct 21 ms 2312 KB Output is correct
14 Correct 15 ms 1920 KB Output is correct
15 Correct 26 ms 3320 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1280 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1280 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1280 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1280 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -