oj.uz

Submission #44077

# Submission time Handle Problem Language Result Execution time Memory
44077 2018-03-29T17:06:34 Z HachikujiMayoi Library (JOI18_library) C++14
19 / 100
 580 ms 844 KB 
#include "library.h"
#include "bits/stdc++.h"

using namespace std;

const int maxN = 1000;

int chosen[maxN + 10];
vector <int> M;

int QUERY(vector <int> &order, int id, int start){
	fill(M.begin(), M.end(), 0);
	for(int i = start; i < order.size(); ++i){
		M[order[i] - 1] = 1;
	}
	M[id - 1] = 1;
	return Query(M) == 1;
}

void Solve(int N){
	srand(time(NULL));
	M.resize(N);
	vector <int> order;
	order.push_back(1);
	chosen[1] = 1;
	while(int(order.size()) < N){
		vector <int> rnd, got, norder;
		for(int i = 1; i <= N; ++i){
			if(chosen[i] == 0){
				rnd.push_back(i);
			}
		}
		random_shuffle(rnd.begin(), rnd.end());
		for(auto id : rnd){
			if(QUERY(order, id, 0)){
				got.push_back(id);
				if(int(got.size()) > 1) break;
			}
		}
		if(int(got.size()) == 1){
			if(int(order.size()) == 1){
				norder.push_back(got[0]);
				norder.push_back(order[0]);
			}
			else{
				if(QUERY(order, got[0], 1)){
					norder.insert(norder.end(), order.begin(), order.end());
					norder.push_back(got[0]);
				}
				else{
					norder.push_back(got[0]);
					norder.insert(norder.end(), order.begin(), order.end());
				}
			}
		}
		else{
			if(int(order.size()) == 1){
				norder.push_back(got[0]);
				norder.push_back(order[0]);
				norder.push_back(got[1]);
			}
			else{
				if(QUERY(order, got[0], 1)){
					swap(got[0], got[1]);
				}
				norder.push_back(got[0]);
				norder.insert(norder.end(), order.begin(), order.end());
				norder.push_back(got[1]);
			}
		}
		order = norder;
		for(auto id : got){
			chosen[id] = 1;
		}
	}
	Answer(order);
}

Compilation message

library.cpp: In function 'int QUERY(std::vector<int>&, int, int)':
library.cpp:13:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = start; i < order.size(); ++i){
                     ~~^~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 248 KB Output is correct
2 Correct 144 ms 308 KB Output is correct
3 Correct 111 ms 352 KB Output is correct
4 Correct 142 ms 352 KB Output is correct
5 Correct 133 ms 372 KB Output is correct
6 Correct 143 ms 392 KB Output is correct
7 Correct 127 ms 392 KB Output is correct
8 Correct 121 ms 460 KB Output is correct
9 Correct 195 ms 460 KB Output is correct
10 Correct 57 ms 460 KB Output is correct
11 Correct 1 ms 480 KB Output is correct
12 Correct 2 ms 480 KB Output is correct
13 Correct 2 ms 480 KB Output is correct
14 Correct 2 ms 524 KB Output is correct
15 Correct 3 ms 576 KB Output is correct
16 Correct 4 ms 576 KB Output is correct

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 248 KB Output is correct
2 Correct 144 ms 308 KB Output is correct
3 Correct 111 ms 352 KB Output is correct
4 Correct 142 ms 352 KB Output is correct
5 Correct 133 ms 372 KB Output is correct
6 Correct 143 ms 392 KB Output is correct
7 Correct 127 ms 392 KB Output is correct
8 Correct 121 ms 460 KB Output is correct
9 Correct 195 ms 460 KB Output is correct
10 Correct 57 ms 460 KB Output is correct
11 Correct 1 ms 480 KB Output is correct
12 Correct 2 ms 480 KB Output is correct
13 Correct 2 ms 480 KB Output is correct
14 Correct 2 ms 524 KB Output is correct
15 Correct 3 ms 576 KB Output is correct
16 Correct 4 ms 576 KB Output is correct
17 Runtime error 580 ms 844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -