제출 #503619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503619		fatemetmhr	도서관 (JOI18_library)	C++17	19 / 100	356 ms	376 KiB

library

//  ~Be name khoda~  //

#include<bits/stdc++.h>
#include "library.h"

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn  =  1e6   + 10;
const int maxn5 =  2e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int per[maxn5];
vector <int> av, as, part, out, adj[maxn5];
bool mark[maxn5];

inline int found_adj(){
	int e = 0;
	for(auto u : as) for(auto v : adj[u]){
		e += out[v - 1];
		//cout << u << ' ';
	}
	e /= 2;
	//cout << " final " << e << endl;
	return int(as.size()) - e;
}

inline bool ask(){
	for(int i = 0; i < out.size(); i++)
		out[i] = 0;
	for(auto u : as)
		out[u - 1] = 1;
	int ans = Query(out);
	return ans < found_adj();
}

inline void parti(){
	for(int i = 0; i < av.size(); i++)
		per[i] = i;
	shuffle(per, per + av.size(), rng);
	as.clear();
	for(int i = 0; i < av.size(); i++)
		if(per[i] <= (av.size() - 1) / 2)
			as.pb(av[i]);
	bool re = ask();
	if(re){
		part.clear();
		for(auto u : as)
			part.pb(u);
		return; 
	}
	//*
	as.clear();
	for(int i = 0; i < av.size(); i++)
		if(per[i] > (av.size() - 1) / 2)
			as.pb(av[i]);
	re = ask();
	if(re){
		part.clear();
		for(auto u : as)
			part.pb(u);
		return; 
	}
	//*/
	parti();
	return;
}

inline pair<int, int> find_adj(){
	if(av.size() == 2) return {av[0], av[1]};
	if(av.size() == 3){
		as.clear();
		as.pb(av[0]);
		as.pb(av[1]);
		bool re = ask();
		if(re) return {av[0], av[1]};
		as.pop_back();
		as.pb(av[2]);
		re = ask();
		if(re) return {av[0], av[2]};
		return {av[1], av[2]};
	}
	parti();
	av.clear();
	for(auto u : part)
		av.pb(u);
	return find_adj();
}

void Solve(int n)
{
	if(n == 1){
		vector <int> ans;
		ans.pb(1);
		Answer(ans);
		return;
	}
	out.resize(n);
	int rem = n - 1;
	while(rem){
		av.clear();
		for(int i = 1; i <= n; i++) if(adj[i].size() < 2)
			av.pb(i);
		pair <int, int> tmp = find_adj();
		adj[tmp.fi].pb(tmp.se);
		adj[tmp.se].pb(tmp.fi);
		//cout << "found out " << tmp.fi << ' ' << tmp.se << " adj " << endl;
		rem--;
	}
	vector <int> ans;
	int v = -1;
	for(int i = 1; i <= n; i++) if(adj[i].size() == 1)
		v = i;
	ans.pb(v);
	mark[v] = true;
	v = adj[v][0];
	while(true){
		ans.pb(v);
		mark[v] = true;
		if(adj[v].size() == 1)
			break;
		int u = adj[v][0];
		if(mark[u])
			u = adj[v][1];
		v = u;
	}
	Answer(ans);
	return;
}

컴파일 시 표준 에러 (stderr) 메시지

library.cpp: In function 'bool ask()':
library.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < out.size(); i++)
      |                 ~~^~~~~~~~~~~~
library.cpp: In function 'void parti()':
library.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:57:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   if(per[i] <= (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
library.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 0; i < av.size(); i++)
      |                 ~~^~~~~~~~~~~
library.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   if(per[i] > (av.size() - 1) / 2)
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 81