oj.uz

Submission #329210

# Submission time Handle Problem Language Result Execution time Memory
329210 2020-11-19T21:27:36 Z NachoLibre Library (JOI18_library) C++14
0 / 100
 46 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;
#include "library.h"

const int N = 1003;
int e[N][2];
vector<int> qv;

int ask(vector<int> v) {
	for(int i = 0; i < qv.size(); ++i) qv[i] = 0;
	for(int i = 0; i <  v.size(); ++i) qv[v[i] - 1] = 1;
	return Query(qv);
}

bool neig(vector<int> v, int x) {
	int a = ask(v);
	v.push_back(x);
	int b = ask(v);
	v.pop_back();
	return(a >= b);
}

void dvd(vector<int> &v, int x) {
	int n = v.size();
	vector<int> l;
	for(int i = 0; i < n / 2; ++i) {
		l.push_back(v[i]);
	}
	if(neig(l, x)) v = l;
	else {
		l.clear();
		for(int i = n / 2; i < n; ++i) {
			l.push_back(v[i]);
		}
		v = l;
	}
}

void Solve(int n) {
	if(n == 1) {
		Answer({1});
		return;
	}
	qv.resize(n);
	vector<int> v;
	for(int i = 2; i <= n; ++i) {
		v.push_back(i);
	}
	int dg = 1;
	while(true) {
		vector<int> u = v;
		while(u.size() > 1) {
			dvd(u, dg);
		}
		if(neig(u, dg)) {
			e[dg][0] = u[0];
			e[u[0]][1] = dg;
			dg = u[0];
			v.erase(find(v.begin(), v.end(), u[0]));
		} else {
			break;
		}
	}
	dg = 1;
	while(v.size()) {
		vector<int> u = v;
		while(u.size() > 1) {
			dvd(u, dg);
		}
		e[dg][1] = u[0];
		e[u[0]][0] = dg;
		dg = u[0];
		v.erase(find(v.begin(), v.end(), u[0]));
	}
	dg = 1;
	while(e[dg][0]) dg = e[dg][0];
	while(dg) {
		v.push_back(dg);
		dg = e[dg][1];
	}
	Answer(v);
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}*/

Compilation message

library.cpp: In function 'int ask(std::vector<int>)':
library.cpp:10:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = 0; i < qv.size(); ++i) qv[i] = 0;
      |                 ~~^~~~~~~~~~~
library.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i = 0; i <  v.size(); ++i) qv[v[i] - 1] = 1;
      |                 ~~^~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 364 KB # of queries: 2600
2 Correct 31 ms 384 KB # of queries: 2506
3 Correct 36 ms 364 KB # of queries: 2712
4 Correct 41 ms 364 KB # of queries: 2628
5 Correct 36 ms 364 KB # of queries: 2774
6 Correct 37 ms 364 KB # of queries: 2634
7 Correct 31 ms 384 KB # of queries: 2768
8 Correct 39 ms 364 KB # of queries: 2678
9 Correct 46 ms 364 KB # of queries: 2582
10 Correct 24 ms 492 KB # of queries: 1602
11 Correct 0 ms 364 KB # of queries: 0
12 Runtime error 1 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 364 KB # of queries: 2600
2 Correct 31 ms 384 KB # of queries: 2506
3 Correct 36 ms 364 KB # of queries: 2712
4 Correct 41 ms 364 KB # of queries: 2628
5 Correct 36 ms 364 KB # of queries: 2774
6 Correct 37 ms 364 KB # of queries: 2634
7 Correct 31 ms 384 KB # of queries: 2768
8 Correct 39 ms 364 KB # of queries: 2678
9 Correct 46 ms 364 KB # of queries: 2582
10 Correct 24 ms 492 KB # of queries: 1602
11 Correct 0 ms 364 KB # of queries: 0
12 Runtime error 1 ms 364 KB Execution killed with signal 13 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -