oj.uz

Submission #44396

# Submission time Handle Problem Language Result Execution time Memory
44396 2018-04-01T16:30:53 Z Bruteforceman Library (JOI18_library) C++14
100 / 100
 642 ms 844 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
bool vis[10000];
vector <int> P, Q;
int size;

void print(vector <int> &M) {
	for(auto i : M) {
		cout << i << " ";
	}
	cout << endl;
}

int query(vector <int> &v) {
	bool good = false;
	for(int i = 0; i < size; i++) {
		if(v[i] == 1) {
			good = true;
			break;
		}
	}
	return good ? Query(v) : 0;
}
bool goodSet(vector <int> &v) {
	vector <int> com (size);
	for(int i = 0; i < size; i++) {
		if(vis[i]) com[i] = 1;
		else com[i] = v[i] ^ 1;
	}
	int p = query(v);
	int q = query(com);
	return (p - 1) != q;
}
bool adjacent(int p, int q) {
	vector <int> v (size);
	v[p] = 1;
	v[q] = 1;
	return query(v) == 1;
}
bool goodSet(int p, int q, vector <int> &v) {
	vector <int> shit (size);
	for(int i = 0; i < size; i++) shit[i] = vis[i];
	for(int i = p; i <= q; i++) shit[v[i]] = 1;
	return goodSet(shit);
}
int search(int b, int e, vector <int> &v) {
	if(b == e) {
		return b;
	}
	int m = (b + e) >> 1;
	if(goodSet(b, m, v)) return search(b, m, v);
	else return search(m + 1, e, v);
}

void Solve(int N)
{
	if(N == 1) {
		vector <int> ans;
		ans.push_back(1);
		Answer(ans);
		return ;
	}
	size = N;
	vector<int> M(N);
	for(int i = 0; i < size; i++) {
		M[i] = i;
	}
	memset(vis, false, sizeof vis);
	vector <int> H (size);
	fill(H.begin(), H.end(), 1);
	for(int i = 0; i < size; i++) {
		H[i] = 0;
		if(query(H) == 1) {
			vis[i] = true;
			M.erase(find(M.begin(), M.end(), i));
			if(P.empty()) P.push_back(i);
			else Q.push_back(i);
		}
		H[i] = 1;
	}
	while(P.size() + Q.size() < N) {
		int can = search(0, M.size() - 1, M);
		int val = M[can];
		if (adjacent(P.back(), val)) P.push_back(val);
		else Q.push_back(val);
		M.erase(M.begin() + can);
		vis[val] = true;
	}
	reverse(Q.begin(), Q.end());
	vector<int> res(N);
	for(int i = 0; i < P.size(); i++) {
		res[i] = P[i] + 1;
	}
	for(int i = 0; i < Q.size(); i++) {
		res[i + P.size()] = Q[i] + 1;
	}
	Answer(res);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:82:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(P.size() + Q.size() < N) {
        ~~~~~~~~~~~~~~~~~~~~^~~
library.cpp:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < P.size(); i++) {
                 ~~^~~~~~~~~~
library.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < Q.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 248 KB Output is correct
2 Correct 41 ms 308 KB Output is correct
3 Correct 39 ms 516 KB Output is correct
4 Correct 42 ms 580 KB Output is correct
5 Correct 37 ms 580 KB Output is correct
6 Correct 34 ms 580 KB Output is correct
7 Correct 33 ms 616 KB Output is correct
8 Correct 45 ms 616 KB Output is correct
9 Correct 52 ms 616 KB Output is correct
10 Correct 19 ms 616 KB Output is correct
11 Correct 2 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 2 ms 616 KB Output is correct
14 Correct 2 ms 616 KB Output is correct
15 Correct 2 ms 616 KB Output is correct
16 Correct 5 ms 616 KB Output is correct

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 248 KB Output is correct
2 Correct 41 ms 308 KB Output is correct
3 Correct 39 ms 516 KB Output is correct
4 Correct 42 ms 580 KB Output is correct
5 Correct 37 ms 580 KB Output is correct
6 Correct 34 ms 580 KB Output is correct
7 Correct 33 ms 616 KB Output is correct
8 Correct 45 ms 616 KB Output is correct
9 Correct 52 ms 616 KB Output is correct
10 Correct 19 ms 616 KB Output is correct
11 Correct 2 ms 616 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 2 ms 616 KB Output is correct
14 Correct 2 ms 616 KB Output is correct
15 Correct 2 ms 616 KB Output is correct
16 Correct 5 ms 616 KB Output is correct
17 Correct 558 ms 616 KB Output is correct
18 Correct 517 ms 616 KB Output is correct
19 Correct 642 ms 616 KB Output is correct
20 Correct 563 ms 716 KB Output is correct
21 Correct 482 ms 716 KB Output is correct
22 Correct 516 ms 844 KB Output is correct
23 Correct 557 ms 844 KB Output is correct
24 Correct 185 ms 844 KB Output is correct
25 Correct 492 ms 844 KB Output is correct
26 Correct 479 ms 844 KB Output is correct
27 Correct 202 ms 844 KB Output is correct
28 Correct 586 ms 844 KB Output is correct
29 Correct 561 ms 844 KB Output is correct
30 Correct 552 ms 844 KB Output is correct