oj.uz

Submission #654629

# Submission time Handle Problem Language Result Execution time Memory
654629 2022-11-01T03:12:12 Z uylulu Library (JOI18_library) C++14
100 / 100
 479 ms 444 KB 
#include<bits/stdc++.h>
#include <cstdio>
#include <vector>
#include "library.h"

using namespace std;

int n;

int ask(vector<int> st) {
	vector<int> num(n,0);
	for(auto u : st) {
		num[u - 1] = 1;
	}
	return Query(num);
}

const int N = 1e3;

int res[N + 1];

vector<int> crr;
bool check[N + 1];

void dnc(int lst) {
	if(crr.size() == 1) {
		res[lst + 1] = crr[0];
		check[res[lst + 1]] = true;
		crr.clear();
		return;
	}
	vector<int> fi,se;
	for(int i = 0;i < crr.size()/2;i++) {
		fi.push_back(crr[i]);
	}
	for(int i = crr.size()/2;i < crr.size();i++) {
		se.push_back(crr[i]);
	}
	int dad = ask(fi);
	fi.push_back(res[lst]);
	int mom = ask(fi);
	if(dad == mom) {
		fi.pop_back();
		crr = fi;
	} else {
		crr = se;
	}
	dnc(lst);
}


void Solve(int len)
{
	n = len;
	if(n == 1) {
		Answer({1});
		return;
	}
	for(int i = 1;i <= n;i++) {
		vector<int> asd;
		for(int j = 1;j <= n;j++) {
			if(i == j) continue;
			asd.push_back(j);
		}
		if(ask(asd) == 1) {
			res[1] = i;
			break;
		}
	}
	check[res[1]] = true;
	for(int i = 2;i <= n;i++) {
		crr.clear();
		for(int j = 1;j <= n;j++) {
			if(!check[j]) {
				crr.push_back(j);
			}
		}
		dnc(i - 1);
	}
	vector<int> kq(n,0);
	for(int i = 0;i < n;i++) {
		kq[i] = res[i + 1];
	}
	Answer(kq);
	return;
}

Compilation message

library.cpp: In function 'void dnc(int)':
library.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0;i < crr.size()/2;i++) {
      |                ~~^~~~~~~~~~~~~~
library.cpp:36:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i = crr.size()/2;i < crr.size();i++) {
      |                           ~~^~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 304 KB # of queries: 2375
2 Correct 43 ms 208 KB # of queries: 2409
3 Correct 43 ms 300 KB # of queries: 2648
4 Correct 38 ms 208 KB # of queries: 2595
5 Correct 38 ms 308 KB # of queries: 2508
6 Correct 37 ms 288 KB # of queries: 2551
7 Correct 34 ms 208 KB # of queries: 2544
8 Correct 42 ms 304 KB # of queries: 2420
9 Correct 68 ms 292 KB # of queries: 2546
10 Correct 22 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 240 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 77
16 Correct 2 ms 208 KB # of queries: 183

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 304 KB # of queries: 2375
2 Correct 43 ms 208 KB # of queries: 2409
3 Correct 43 ms 300 KB # of queries: 2648
4 Correct 38 ms 208 KB # of queries: 2595
5 Correct 38 ms 308 KB # of queries: 2508
6 Correct 37 ms 288 KB # of queries: 2551
7 Correct 34 ms 208 KB # of queries: 2544
8 Correct 42 ms 304 KB # of queries: 2420
9 Correct 68 ms 292 KB # of queries: 2546
10 Correct 22 ms 208 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 240 KB # of queries: 1
13 Correct 1 ms 208 KB # of queries: 4
14 Correct 0 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 77
16 Correct 2 ms 208 KB # of queries: 183
17 Correct 469 ms 328 KB # of queries: 17982
18 Correct 397 ms 320 KB # of queries: 17293
19 Correct 436 ms 444 KB # of queries: 17467
20 Correct 403 ms 444 KB # of queries: 16325
21 Correct 394 ms 328 KB # of queries: 15324
22 Correct 479 ms 444 KB # of queries: 17669
23 Correct 438 ms 332 KB # of queries: 17224
24 Correct 119 ms 360 KB # of queries: 7915
25 Correct 395 ms 332 KB # of queries: 17136
26 Correct 387 ms 444 KB # of queries: 15963
27 Correct 164 ms 308 KB # of queries: 8040
28 Correct 379 ms 320 KB # of queries: 15957
29 Correct 406 ms 332 KB # of queries: 15939
30 Correct 413 ms 320 KB # of queries: 15957