oj.uz

Submission #482750

# Submission time Handle Problem Language Result Execution time Memory
482750 2021-10-26T08:41:22 Z rk42745417 Mouse (info1cup19_mouse) C++17
34 / 100
 146 ms 200 KB 
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = ll(2e18) + ll(1e15);
const double EPS = 1e-8;

int query(vector<int>);

void solve(int n) {
	vector<int> arr(n);
	vector<bool> fixed(n);
	for(int i = 0; i < n; i++)
		arr[i] = i + 1;
	for(int i = 0; i < n; i++) {
		if(fixed[i])
			continue;
		int w = query(arr);
		if(w == n)
			return;
		bool ok = 0;

		int tot = 0, neg = 0;
		int a = -1, b = -1;

		for(int j = 0; j < n; j++) {
			if(i == j)
				continue;
			swap(arr[i], arr[j]);
			int x = query(arr);
			swap(arr[i], arr[j]);
			if(x == n)
				return;

			if(fixed[j]) {
				if(x - w == -2) {
					fixed[i] = true;
					ok = 1;
					break;
				}
				continue;
			}
			tot++;

			if(x - w == 2) {
				swap(arr[i], arr[j]);
				fixed[i] = fixed[j] = true;
				ok = 1;
				break;
			}
			if(x - w == 1) {
				if(a == -1)
					a = j;
				else if(b == -1)
					b = j;
				else
					assert(false);
			}
			if(x - w == -1) {
				neg++;
			}
			if(x - w == -2) {
				fixed[i] = fixed[j] = true;
				ok = 1;
				break;
			}
		}
		if(ok)
			continue;
		if(tot == neg)
			fixed[i] = true;
		assert(b != -1);
		swap(arr[i], arr[a]);
		swap(arr[i], arr[b]);
		int x = query(arr);
		if(x == n)
			return;
		if(x - w >= 2) {
			fixed[i] = fixed[a] = true;
			if(x - w == 3)
				fixed[b] = true;
		}
		else {
			swap(arr[i], arr[b]);
			swap(arr[i], arr[a]);
			swap(arr[i], arr[b]);
			swap(arr[i], arr[a]);
			fixed[i] = fixed[b] = true;
			if(x - w == 1)
				fixed[a] = true;
		}
		//cout << "owo " << a << ' ' << b << '\n';;
	}
	query(arr);
}

/*
vector<int> arr;
int query(vector<int> g) {
	int w = 0;
	for(int i = 0; i < g.size(); i++)
		w += arr[i] == g[i];
	cout << "query: ";
	for(int a : g)
		cout << a << ' ';
	cout << '\n';
	cout << "Answer: " << w << '\n';
	return w;
}
signed main() {
	int n;
	cin >> n;
	arr.resize(n);
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	solve(n);
}
*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 0 ms 200 KB Correct! Number of queries: 8
3 Correct 0 ms 200 KB Correct! Number of queries: 19
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 18
6 Correct 1 ms 200 KB Correct! Number of queries: 15

Subtask #2
21.000016 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 0 ms 200 KB Correct! Number of queries: 8
3 Correct 0 ms 200 KB Correct! Number of queries: 19
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 18
6 Correct 1 ms 200 KB Correct! Number of queries: 15
7 Correct 18 ms 200 KB Correct! Number of queries: 1300
8 Correct 18 ms 200 KB Correct! Number of queries: 1300
9 Correct 15 ms 200 KB Correct! Number of queries: 1100
10 Correct 17 ms 200 KB Correct! Number of queries: 1300
11 Correct 11 ms 200 KB Correct! Number of queries: 900
12 Correct 13 ms 200 KB Correct! Number of queries: 1300
13 Correct 11 ms 200 KB Correct! Number of queries: 1100
14 Correct 17 ms 200 KB Correct! Number of queries: 1300
15 Correct 15 ms 200 KB Correct! Number of queries: 1200
16 Correct 14 ms 200 KB Correct! Number of queries: 1200

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Correct! Number of queries: 24
2 Correct 0 ms 200 KB Correct! Number of queries: 8
3 Correct 0 ms 200 KB Correct! Number of queries: 19
4 Correct 1 ms 200 KB Correct! Number of queries: 24
5 Correct 1 ms 200 KB Correct! Number of queries: 18
6 Correct 1 ms 200 KB Correct! Number of queries: 15
7 Correct 18 ms 200 KB Correct! Number of queries: 1300
8 Correct 18 ms 200 KB Correct! Number of queries: 1300
9 Correct 15 ms 200 KB Correct! Number of queries: 1100
10 Correct 17 ms 200 KB Correct! Number of queries: 1300
11 Correct 11 ms 200 KB Correct! Number of queries: 900
12 Correct 13 ms 200 KB Correct! Number of queries: 1300
13 Correct 11 ms 200 KB Correct! Number of queries: 1100
14 Correct 17 ms 200 KB Correct! Number of queries: 1300
15 Correct 15 ms 200 KB Correct! Number of queries: 1200
16 Correct 14 ms 200 KB Correct! Number of queries: 1200
17 Runtime error 146 ms 200 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -