Submission #58726

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58726	2018-07-19T03:21:30 Z	ksun48	Library (JOI18_library)	C++14	19 / 100	755 ms	688 KB

library

#include "library.h"
#include <bits/stdc++.h>
using namespace std;

int check(int n, int a, int b){
	vector<int> ask(n, 0);
	ask[a] = ask[b] = 1;
	if(Query(ask) == 1){
		return 1;
	}
	return 0;
}

void Solve(int N) {
	int n = N;
	vector<vector<int> > groups;
	for(int i = 0; i < n; i++){
		groups.push_back({i});
	}
	while(groups.size() > 1){
		vector<int> inside;
		for(int j = 0; j < groups.size(); j++){
			inside.push_back(j);
		}
		while(inside.size() > 2){
			vector<int> newinside;
			int bb = max(2, min((int)inside.size()-1, (int)sqrt(inside.size()) + 1));
			//cout << inside.size() << " " << bb << endl;
			random_shuffle(inside.begin(), inside.end());
			for(int i = 0; i < bb; i++){
				newinside.push_back(inside[i]);
			}

			vector<int> ask(n, 0);
			for(int x : newinside){
				for(int a : groups[x]){
					ask[a] = 1;
				}
			}
			int b = Query(ask);
			//assert(b <= newn1);
			if(b < bb){
				inside = newinside;
			}
		}
		vector<vector<int> > newgroups;
		vector<vector<int> > good;
		for(int i = 0; i < groups.size(); i++){
			if(i != inside[0] && i != inside[1]){
				newgroups.push_back(groups[i]);
			} else {
				good.push_back(groups[i]);
			}
		}
		vector<int> ans;
		if(check(n, good[0][0], good[1][0])){
			reverse(good[0].begin(), good[0].end());
		} else if(check(n, good[0][good[0].size() - 1], good[1][0])){
		} else if(check(n, good[0][0], good[1][good[1].size()-1])){
			reverse(good[0].begin(), good[0].end());
			reverse(good[1].begin(), good[1].end());
		} else if(check(n, good[0][good[0].size() - 1], good[1][good[1].size() - 1])){
			reverse(good[1].begin(), good[1].end());			
		} else {
			//assert(0);
		}
		ans.insert(ans.end(), good[0].begin(), good[0].end());
		ans.insert(ans.end(), good[1].begin(), good[1].end());
		newgroups.push_back(ans);
		groups = newgroups;
	}
	vector<int> ans = groups[0];
	for(int j = 0; j < ans.size(); j++){
		ans[j]++;
		//cout << ans[j] << " ";
	}
	//cout << endl;
	Answer(ans);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < groups.size(); j++){
                  ~~^~~~~~~~~~~~~~~
library.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < groups.size(); i++){
                  ~~^~~~~~~~~~~~~~~
library.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 0; j < ans.size(); j++){
                 ~~^~~~~~~~~~~~

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	248 KB	Output is correct
2	Correct	69 ms	308 KB	Output is correct
3	Correct	49 ms	528 KB	Output is correct
4	Correct	39 ms	528 KB	Output is correct
5	Correct	39 ms	528 KB	Output is correct
6	Correct	73 ms	528 KB	Output is correct
7	Correct	80 ms	528 KB	Output is correct
8	Correct	73 ms	528 KB	Output is correct
9	Correct	49 ms	624 KB	Output is correct
10	Correct	40 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	2 ms	624 KB	Output is correct
13	Correct	2 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	5 ms	624 KB	Output is correct

Subtask #2

0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	248 KB	Output is correct
2	Correct	69 ms	308 KB	Output is correct
3	Correct	49 ms	528 KB	Output is correct
4	Correct	39 ms	528 KB	Output is correct
5	Correct	39 ms	528 KB	Output is correct
6	Correct	73 ms	528 KB	Output is correct
7	Correct	80 ms	528 KB	Output is correct
8	Correct	73 ms	528 KB	Output is correct
9	Correct	49 ms	624 KB	Output is correct
10	Correct	40 ms	624 KB	Output is correct
11	Correct	2 ms	624 KB	Output is correct
12	Correct	2 ms	624 KB	Output is correct
13	Correct	2 ms	624 KB	Output is correct
14	Correct	2 ms	624 KB	Output is correct
15	Correct	3 ms	624 KB	Output is correct
16	Correct	5 ms	624 KB	Output is correct
17	Incorrect	755 ms	688 KB	Wrong Answer [3]
18	Halted	0 ms	0 KB	-