oj.uz

답안 #58725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58725 2018-07-19T03:16:19 Z ksun48 도서관 (JOI18_library) C++14
19 / 100
 873 ms 660 KB 
#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(groups.size(), 1);
		int n1 = groups.size();
		while(n1 > 2){
			vector<int> newinside(groups.size());
			vector<int> ask(n, 0);
			int newn1 = 0;
			int bb = sqrt(n1) + 1;
			for(int i = 0; i < groups.size(); i++){
				if(inside[i]){
					newinside[i] = (rand() % bb == 0);
					if(newinside[i]){
						newn1++;
					}
				}
			}
			if(newn1 <= 1 || newn1 == n1) continue;
			for(int i = 0; i < groups.size(); i++){
				if(newinside[i]){
					for(int a : groups[i]){
						ask[a] = 1;
					}
				}
			}
			int b = Query(ask);
			//assert(b <= newn1);
			if(b < newn1){
				n1 = newn1;
				inside = newinside;
			}
		}
		vector<vector<int> > newgroups;
		vector<vector<int> > good;
		for(int i = 0; i < groups.size(); i++){
			if(!inside[i]){
				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:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < groups.size(); i++){
                   ~~^~~~~~~~~~~~~~~
library.cpp:37:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < groups.size(); i++){
                   ~~^~~~~~~~~~~~~~~
library.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < groups.size(); i++){
                  ~~^~~~~~~~~~~~~~~
library.cpp:78: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

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 248 KB Output is correct
2 Correct 38 ms 392 KB Output is correct
3 Correct 63 ms 392 KB Output is correct
4 Correct 93 ms 392 KB Output is correct
5 Correct 91 ms 432 KB Output is correct
6 Correct 96 ms 508 KB Output is correct
7 Correct 54 ms 660 KB Output is correct
8 Correct 96 ms 660 KB Output is correct
9 Correct 69 ms 660 KB Output is correct
10 Correct 30 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 KB Output is correct
15 Correct 3 ms 660 KB Output is correct
16 Correct 4 ms 660 KB Output is correct

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 248 KB Output is correct
2 Correct 38 ms 392 KB Output is correct
3 Correct 63 ms 392 KB Output is correct
4 Correct 93 ms 392 KB Output is correct
5 Correct 91 ms 432 KB Output is correct
6 Correct 96 ms 508 KB Output is correct
7 Correct 54 ms 660 KB Output is correct
8 Correct 96 ms 660 KB Output is correct
9 Correct 69 ms 660 KB Output is correct
10 Correct 30 ms 660 KB Output is correct
11 Correct 2 ms 660 KB Output is correct
12 Correct 2 ms 660 KB Output is correct
13 Correct 2 ms 660 KB Output is correct
14 Correct 2 ms 660 KB Output is correct
15 Correct 3 ms 660 KB Output is correct
16 Correct 4 ms 660 KB Output is correct
17 Incorrect 873 ms 660 KB Wrong Answer [3]
18 Halted 0 ms 0 KB -