oj.uz

Submission #315282

# Submission time Handle Problem Language Result Execution time Memory
315282 2020-10-22T08:34:32 Z Seanliu Mouse (info1cup19_mouse) C++14
9 / 100
 3000 ms 512 KB 
#include <iostream>
#include <vector>
#include "grader.h"
using namespace std;

const int maxN = 326;
int ans[maxN], ANS[maxN], N;
bool has[maxN], found;

/*
int query(vector<int> q){
	int ans = 0;
	cout << "Asking: ";
	for(int i = 0; i < N; i++){
		cout << q[i] << " ";
		ans += (q[i] == ANS[i]);
	}
	cout << ": " << ans << endl;
	return ans;
}
*/

bool dfs(int now, int N){
	if(found) return true;
	vector<int> q;
	vector<int>().swap(q);
	if(now == N){
		for(int i = 0; i < N; i++) q.push_back(ans[i]);
		if(query(q) == N){
			found = true;
			return true;
		}
		return false;
	}
	for(int j = 0; j < now; j++){
		//cout << "ans[" << j << "] = " << ans[j] << endl;
		q.push_back(ans[j]); 
	}
	for(int j = 1; j <= N; j++) if(!has[j]){
		q.push_back(j);
	}
	if(found) return true;
	int baseline = query(q);
	if(baseline == N) return true;
	vector<int> asked;
	asked.clear();
	asked.push_back(now);
	for(int j = now + 1; j < N; j++){
		swap(q[j], q[now]);
		if(found) return true;
		int res = query(q);
		if(res == N) return true;
		if(res > baseline){
			asked.clear();
			asked.push_back(j);
			baseline = res;
		} else if(res == baseline){
			asked.push_back(j);
		}
		swap(q[j], q[now]);
	}
	for(int x : asked){
		///cout << "x = " << x << endl;
		has[q[x]] = true;
		ans[now] = q[x];
		if(dfs(now + 1, N)) {
			//cout << "ans[" << now << "] = " << q[x] << endl; 
			return true;
		}
		has[q[x]] = false;
	}
	return false;
}

void solve(int N){
	dfs(0, N);
}

/*
int main(){
	cin >> N;
	for(int i = 0; i < N; i++) cin >> ANS[i];
	solve(N);
}
*/

Subtask #1
9.000004 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 74
2 Correct 0 ms 256 KB Correct! Number of queries: 7
3 Correct 1 ms 256 KB Correct! Number of queries: 20
4 Correct 1 ms 256 KB Correct! Number of queries: 25
5 Correct 1 ms 256 KB Correct! Number of queries: 66
6 Correct 1 ms 256 KB Correct! Number of queries: 27

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 74
2 Correct 0 ms 256 KB Correct! Number of queries: 7
3 Correct 1 ms 256 KB Correct! Number of queries: 20
4 Correct 1 ms 256 KB Correct! Number of queries: 25
5 Correct 1 ms 256 KB Correct! Number of queries: 66
6 Correct 1 ms 256 KB Correct! Number of queries: 27
7 Execution timed out 3067 ms 512 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 74
2 Correct 0 ms 256 KB Correct! Number of queries: 7
3 Correct 1 ms 256 KB Correct! Number of queries: 20
4 Correct 1 ms 256 KB Correct! Number of queries: 25
5 Correct 1 ms 256 KB Correct! Number of queries: 66
6 Correct 1 ms 256 KB Correct! Number of queries: 27
7 Execution timed out 3067 ms 512 KB Time limit exceeded
8 Halted 0 ms 0 KB -