oj.uz

답안 #331114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
331114 2020-11-27T12:15:02 Z pit4h 도서관 (JOI18_library) C++14
19 / 100
 397 ms 664 KB 
#include<bits/stdc++.h>
#include "library.h"
using namespace std;
using vi = vector<int>;

int n;

int qry(int x, int y) {
	vector<int> M(n);
	M[x-1] = M[y-1] = 1;
	return Query(M);
}
int qry(vi v1, vi v2) {
	vector<int> M(n);
	for(int i: v1) M[i-1] = 1;
	for(int i: v2) M[i-1] = 1;
	return Query(M);
}
vector<vi> solve(vector<vi> vec) {
	if((int)vec.size()==1) {
		return vec;
	}
	int sz = vec.size();
	vector<vi> v1, v2;
	for(int i=0; i<sz/2; ++i) {
		v1.push_back(vec[i]);
	}
	for(int i=sz/2; i<sz; ++i) {
		v2.push_back(vec[i]);
	}
	v1 = solve(v1);
	v2 = solve(v2);
	for(auto v: v1) {
		vector<vi> new_v2;
		for(auto V: v2) {
			if(qry(v, V)==1) {
				if(qry(v.back(), V.back())==1) {
					reverse(V.begin(), V.end());
				}
				else if(qry(v[0], V[0])==1) {
					reverse(v.begin(), v.end());
				}
				else if(qry(v[0], V.back())==1) {
					reverse(v.begin(), v.end());
					reverse(V.begin(), V.end());
				}
				for(int i: V) {
					v.push_back(i);
				}
			}
			else {
				new_v2.push_back(V);
			}
		}
		new_v2.push_back(v);
		v2 = new_v2;
	}
	return v2;
}
void Solve(int N)
{
	n = N;
	vector<vi> vec(N);
	for(int i=0; i<n; ++i) {
		vec[i].push_back(i+1);
	}
	auto res = solve(vec);
	Answer(res.back());
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 364 KB # of queries: 10237
2 Correct 147 ms 576 KB # of queries: 10538
3 Correct 152 ms 364 KB # of queries: 10622
4 Correct 147 ms 364 KB # of queries: 10376
5 Correct 164 ms 364 KB # of queries: 11063
6 Correct 158 ms 492 KB # of queries: 10783
7 Correct 175 ms 384 KB # of queries: 9983
8 Correct 103 ms 492 KB # of queries: 8939
9 Correct 169 ms 492 KB # of queries: 11284
10 Correct 49 ms 492 KB # of queries: 4753
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 72
16 Correct 4 ms 364 KB # of queries: 229

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 364 KB # of queries: 10237
2 Correct 147 ms 576 KB # of queries: 10538
3 Correct 152 ms 364 KB # of queries: 10622
4 Correct 147 ms 364 KB # of queries: 10376
5 Correct 164 ms 364 KB # of queries: 11063
6 Correct 158 ms 492 KB # of queries: 10783
7 Correct 175 ms 384 KB # of queries: 9983
8 Correct 103 ms 492 KB # of queries: 8939
9 Correct 169 ms 492 KB # of queries: 11284
10 Correct 49 ms 492 KB # of queries: 4753
11 Correct 0 ms 364 KB # of queries: 0
12 Correct 0 ms 364 KB # of queries: 2
13 Correct 1 ms 364 KB # of queries: 6
14 Correct 1 ms 364 KB # of queries: 9
15 Correct 2 ms 364 KB # of queries: 72
16 Correct 4 ms 364 KB # of queries: 229
17 Runtime error 397 ms 664 KB Execution killed with signal 13 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -