oj.uz

Submission #315077

# Submission time Handle Problem Language Result Execution time Memory
315077 2020-10-22T02:13:08 Z Kevin_Zhang_TW Mouse (info1cup19_mouse) C++17
40.6667 / 100
 347 ms 384 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
using namespace std;
using ll = long long;
const int MAX_N = 300;
int n;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
vector<int> p{1,2,3,4,5,6,7,8,9,10,11,12,13};
int qcnt;
int query(vector<int> q) { 
	++qcnt;
	int res = 0;
	for (int i = 0;i < n;++i) 
		res += p[i] == q[i];
	if (res == n)
		DE(n, qcnt);
	return res;
}
#else
#define DE(...) 0
void debug(...) {}
#include "grader.h"
#endif
random_device rd;
mt19937 gen(rd());
void solve(int N) {
	n = N;
	vector<int> q(n);
	vector<bool> done(n);
	iota(AI(q), 1);
	shuffle(AI(q), gen);

	int cnt = query(q);
	for (int i = 0;i < n && cnt < n;++i) {
		if (done[i]) continue;
		vector<int> good;
		for (int j = i+1;j < n && cnt < n;++j) {
			if (done[j]) continue;
			swap(q[i], q[j]);
			int v = query(q);
			swap(q[i], q[j]);
			if (v > cnt) {
				swap(q[i], q[j]);
				cnt = v;
				good.pb(j);
				continue;
			}
			if (v == cnt - 2) {
				done[i] = done[j] = true;
				break;
			}
		}
		if (good.size() < 2) continue;
		good.pop_back();
		for (int u : good)
			done[u] = true;

	}
}
#ifdef KEV
int main() {
	solve(p.size());
}
#endif

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 8
2 Correct 0 ms 256 KB Correct! Number of queries: 6
3 Correct 1 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 17
5 Correct 1 ms 256 KB Correct! Number of queries: 17
6 Correct 1 ms 256 KB Correct! Number of queries: 14

Subtask #2
27.66666 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 8
2 Correct 0 ms 256 KB Correct! Number of queries: 6
3 Correct 1 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 17
5 Correct 1 ms 256 KB Correct! Number of queries: 17
6 Correct 1 ms 256 KB Correct! Number of queries: 14
7 Correct 9 ms 256 KB Correct! Number of queries: 700
8 Correct 11 ms 256 KB Correct! Number of queries: 700
9 Correct 8 ms 256 KB Correct! Number of queries: 600
10 Correct 12 ms 256 KB Correct! Number of queries: 700
11 Correct 9 ms 256 KB Correct! Number of queries: 500
12 Correct 8 ms 256 KB Correct! Number of queries: 600
13 Correct 6 ms 256 KB Correct! Number of queries: 700
14 Correct 12 ms 256 KB Correct! Number of queries: 800
15 Correct 9 ms 256 KB Correct! Number of queries: 700
16 Correct 6 ms 256 KB Correct! Number of queries: 600

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 8
2 Correct 0 ms 256 KB Correct! Number of queries: 6
3 Correct 1 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 17
5 Correct 1 ms 256 KB Correct! Number of queries: 17
6 Correct 1 ms 256 KB Correct! Number of queries: 14
7 Correct 9 ms 256 KB Correct! Number of queries: 700
8 Correct 11 ms 256 KB Correct! Number of queries: 700
9 Correct 8 ms 256 KB Correct! Number of queries: 600
10 Correct 12 ms 256 KB Correct! Number of queries: 700
11 Correct 9 ms 256 KB Correct! Number of queries: 500
12 Correct 8 ms 256 KB Correct! Number of queries: 600
13 Correct 6 ms 256 KB Correct! Number of queries: 700
14 Correct 12 ms 256 KB Correct! Number of queries: 800
15 Correct 9 ms 256 KB Correct! Number of queries: 700
16 Correct 6 ms 256 KB Correct! Number of queries: 600
17 Incorrect 347 ms 384 KB Too many queries
18 Halted 0 ms 0 KB -