oj.uz

Submission #315217

# Submission time Handle Problem Language Result Execution time Memory
315217 2020-10-22T04:51:09 Z Kevin_Zhang_TW Mouse (info1cup19_mouse) C++17
40.6667 / 100
 321 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, holan = 5;
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{2,3,4,1,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, res);
	return res;
}
#else
#define DE(...) 0
void debug(...) {}
#include "grader.h"
#endif
random_device rd;
mt19937 gen(rd());
// [ first = ids, second = qs
vector<int> allv;
int allcnt;
int ra(int l, int r) {
	return uniform_int_distribution<int>(l, r)(gen);
}
bool correct(int pos) {
	int oc = allcnt, cnt;
	for (int i = 0;i < 3;++i) {
		int j = n - i - 1;
		swap(allv[pos], allv[j]);
		int v = query(allv);
		if (v < oc) ++ cnt;
		swap(allv[pos], allv[j]);
	}
	return oc >= 2;
}
pair<vector<int>, vector<int>> dfs(vector<int> id, vector<int> q) {
	if (id.empty()) return {{},{}};
	int n = id.size();
	assert(id.size() == q.size());
	DE(n);
	debug(AI(id));
	debug(AI(q));
	if (n == 1) {
		allv[ id[0] ] = q[0] ;
		if (correct(id[0])) 
			return {{},{}};
		return {id, q};
	}
	for (int i = 0;i < n;++i)
		allv[ id[i] ] = q[i];
	int m = n/2;
	vector<int> lid, rid, lq, rq;
	for (int i = 0;i < n;++i)
		if (i < m)
			lid.pb(id[i]), lq.pb(q[i]);
		else
			rid.pb(id[i]), rq.pb(q[i]);
	tie(lid, lq) = dfs(lid, lq);
	tie(rid, rq) = dfs(rid, rq);
	swap(lid, rid);
	auto [a, b] = dfs(lid, lq);
	auto [c, d] = dfs(rid, rq);
	a.insert(a.end(), AI(c));
	b.insert(b.end(), AI(d));
	return {a, b};
}
void solve2(int n) {
	vector<int> id(n), q(n), qq(n);
	allv.resize(n);
	iota(AI(q), 1);
	iota(AI(id), 0);

	int oc = n+n;
	for (int a = 1;a <= 3;++a)
		for (int b = 1;b <= 3;++b)
			for (int c = 1;c <= 3;++c) 
				if (set<int>{a,b,c}.size() == 3) {
					q[0] = a, q[1] = b, q[2] = c;
					int v = query(q);
					if (v < oc)
						oc = v, qq = q;
				}
	assert(oc < n+n);
	q = qq;
	q.erase(q.begin(), q.begin()+3);
	id.erase(id.begin(), id.begin()+3);

	allcnt = oc;

	auto [a, b] = dfs(id, q);

	cerr << "DFS END\n";
	q = allv;
	for (int a = 1;a <= 3;++a)
		for (int b = 1;b <= 3;++b)
			for (int c = 1;c <= 3;++c) 
				if (set<int>{a,b,c}.size() == 3) {
					q[0] = a, q[1] = b, q[2] = c;
					int v = query(q);
					DE(v);
					debug(AI(q));
					if (v == n) break;
				}

}
void solve(int N) {
	n = N;
	vector<int> q(n);
	vector<bool> done(n);
	allv.resize(n);
	iota(AI(q), 1);
	int cnt = query(q);
	if (n > 5) {
		for (int a = n;a > n-3;--a)
			for (int b = n;b > n-3;--b)
				for (int c = n;c > n-3;--c) {
					if (set<int>{a,b,c}.size() < 3) continue;
					vector<int> tmp = q;
					int x = n-1, y = n-2, z = n-3;
					tmp[x] = a, tmp[y] = b, tmp[z] = c;
					int v = query(tmp);
					if (v < cnt) {
						cnt = v;
						q = tmp;
					}
				}
		allcnt = cnt;
		allv = q;
	if (false)	for (int i = 0;i < n-3;++i)
			done[i] = correct(i);
	}

	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]);
				good.pb(j);
				if (v == cnt + 2) {
					good.pb(0);
					cnt = v;
					break;
				}
				cnt = v;
				continue;
			}
			if (v == cnt - 2) {
				done[i] = done[j] = true;
				break;
			}
		}
		if (good.empty()) continue;
		good.pop_back();
		for (int u : good)
			done[u] = true;
	}
}
#ifdef KEV
int main() {
	solve(p.size());
}
#endif

Compilation message

mouse.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > dfs(std::vector<int>, std::vector<int>)':
mouse.cpp:25:17: warning: statement has no effect [-Wunused-value]
   25 | #define DE(...) 0
      |                 ^
mouse.cpp:52:2: note: in expansion of macro 'DE'
   52 |  DE(n);
      |  ^~
mouse.cpp: In function 'void solve2(int)':
mouse.cpp:25:17: warning: statement has no effect [-Wunused-value]
   25 | #define DE(...) 0
      |                 ^
mouse.cpp:112:6: note: in expansion of macro 'DE'
  112 |      DE(v);
      |      ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct! Number of queries: 16
2 Correct 1 ms 256 KB Correct! Number of queries: 6
3 Correct 1 ms 256 KB Correct! Number of queries: 19
4 Correct 1 ms 256 KB Correct! Number of queries: 20
5 Correct 1 ms 256 KB Correct! Number of queries: 16
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 384 KB Correct! Number of queries: 16
2 Correct 1 ms 256 KB Correct! Number of queries: 6
3 Correct 1 ms 256 KB Correct! Number of queries: 19
4 Correct 1 ms 256 KB Correct! Number of queries: 20
5 Correct 1 ms 256 KB Correct! Number of queries: 16
6 Correct 1 ms 256 KB Correct! Number of queries: 14
7 Correct 12 ms 256 KB Correct! Number of queries: 800
8 Correct 10 ms 256 KB Correct! Number of queries: 700
9 Correct 8 ms 256 KB Correct! Number of queries: 700
10 Correct 14 ms 256 KB Correct! Number of queries: 800
11 Correct 8 ms 256 KB Correct! Number of queries: 600
12 Correct 11 ms 384 KB Correct! Number of queries: 800
13 Correct 9 ms 384 KB Correct! Number of queries: 600
14 Correct 12 ms 256 KB Correct! Number of queries: 800
15 Correct 8 ms 256 KB Correct! Number of queries: 600
16 Correct 10 ms 256 KB Correct! Number of queries: 700

Subtask #3
0.0 / 49.0

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