Submission #46013

#	Time	Username	Problem	Language	Result	Execution time	Memory
46013		Mamnoon_Siam	Library (JOI18_library)	C++17	0 / 100	52 ms	1084 KiB

library

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

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

const int maxn = 10010;

int n;
vector<ii> adj;
vector<int> g[maxn];
int cnt[maxn];

bool has(int l, int r) {
	vector<int>v(n);
	//debug(l), debug(r);
	for(int i=l; i<=r; i++) {
		v[i] = 1;
	}
	for(ii &b : adj) {
		if(!v[b.first] or !v[b.second]) continue;
		int x, y;
		tie(x, y) = b;
		if(cnt[x] == 2 or cnt[y] == 2) {
			v[cnt[x] == 2 ? x : y] = 0;
		} else if(cnt[x] == 1 and cnt[y] == 1) {
			v[cnt[x] == 1 ? x : y] = 0;
		}
	} int c = 0;
	//for(int b : v) cout<<b<<' '; cout<<endl;
	for(int i=1; i<=n; i++) {
		c += v[i-1];
	}
	if(c == 0) return false;
	int ret = Query(v); ret--;
	//debug(ret);
	if(ret < c - 1) return true;
	return false;
}

bool connected(int x, int y) {
	vector<int>v(n);
	v[x] = v[y] = 1;
	int ret = Query(v);
	ret--; return !ret;
}

void dfs(int p, int u, vector<int> &v) {
	v.push_back(u);
	for(int b : g[u]) {
		if(b - p) {
			dfs(u, b, v);
		}
	}
}

void Solve(int N) {
	n = N;
	while(adj.size() < n-2) {
		int lo = 0, hi = n-1, l, r;
		while(lo <= hi) {
			int mid = lo + hi >> 1;
			int temp = has(0, mid);
			//cout<<"["<<0<<","<<mid<<"] = "<<temp<<endl;
			if(temp) {
				r = mid;
				hi = mid-1;
			} else {
				lo = mid+1;
			}
		}
		lo = 0, hi = r-1;
		while(lo <= hi) {
			int mid = lo + hi >> 1;
			int temp = has(mid, r);
			//cout<<"["<<mid<<","<<r<<"] = "<<temp<<endl;
			if(temp) {
				l = mid;
				lo = mid + 1;
			} else {
				hi = mid-1;
			}
		}
		//cout<<"Found !!!! Done !!!! ====> "<<l<<" *** "<<r<<endl;
		adj.push_back(ii(l, r));
		cnt[l]++;
		cnt[r]++;
	}
	vector<int> shit;
	for(int i=0; i<n; i++)
		if(cnt[i] == 1) shit.push_back(i);
	sort(all(shit));
	if(shit.size() == 4) {
		for(int i=0; i<4; i++) {
			for(int j=i+1; j<4; j++) {
				int x = shit[i], y = shit[j];
				if(binary_search(all(adj), ii(x, y)) or binary_search(all(adj), ii(y, x)))
					continue;
				if(connected(x, y)) {
					adj.push_back(ii(x, y));
					cnt[x]++, cnt[y]++;
					goto hell;
				}
			}
		}
		hell : ;
	}
	else {
		int z;
		for(int i=0; i<n; i++)
			if(cnt[i] == 0)
				z = i;
		int x = shit[0], y = shit[1];
		cnt[x]++;
		if(connected(x, z)) {
			adj.push_back(ii(x, z));
			cnt[x]++;
		} else {
			adj.push_back(ii(y, z));
			cnt[y]++;
		}
	}
	for(ii &b : adj) {
		g[b.first].push_back(b.second);
		g[b.second].push_back(b.first);
	}
	vector<int> final;
	for(int i=0; i<n; i++) {
		if(cnt[i] == 1) {
			dfs(-1, i, final);
			break;
		}
	}
	/*for(ii &b : adj) {
		cout<<"b = "<<"("<<b.first<<","<<b.second<<")"<<endl;
	}*/
	for(int &b : final) b++;
	Answer(final);
}

Compilation message (stderr)

library.cpp: In function 'int myrand(int, int)':
library.cpp:14:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
library.cpp:14:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(adj.size() < n-2) {
        ~~~~~~~~~~~^~~~~
library.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
library.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1;
              ~~~^~~~
library.cpp:133:15: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(connected(x, z)) {
      ~~~~~~~~~^~~~~~
library.cpp:104:8: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   cnt[l]++;
   ~~~~~^
library.cpp:90:14: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   lo = 0, hi = r-1;
           ~~~^~~~~

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