oj.uz

Submission #237159

# Submission time Handle Problem Language Result Execution time Memory
237159 2020-06-04T22:23:38 Z mode149256 Gondola (IOI14_gondola) C++14
45 / 100
 25 ms 3448 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[])
{
	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 1408 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 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 10 ms 1408 KB Output is correct
7 Correct 17 ms 1792 KB Output is correct
8 Correct 15 ms 1536 KB Output is correct
9 Correct 8 ms 1408 KB Output is correct
10 Correct 17 ms 1664 KB Output is correct

Subtask #3
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 6 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 10 ms 1536 KB Output is correct
7 Correct 19 ms 1664 KB Output is correct
8 Correct 14 ms 1536 KB Output is correct
9 Correct 8 ms 1408 KB Output is correct
10 Correct 18 ms 1664 KB Output is correct
11 Incorrect 5 ms 1280 KB Output isn't correct
12 Halted 0 ms 0 KB -

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 1408 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 7 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 6 ms 1408 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 1408 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 5 ms 1408 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 6 ms 1408 KB Output is correct
11 Correct 16 ms 2432 KB Output is correct
12 Correct 18 ms 2560 KB Output is correct
13 Correct 21 ms 2440 KB Output is correct
14 Correct 16 ms 2432 KB Output is correct
15 Correct 25 ms 3448 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 5 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 1408 KB Integer -3 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -