Submission #707149

#	Time	Username	Problem	Language	Result	Execution time	Memory
707149		minhcool	ICC (CEOI16_icc)	C++17	0 / 100	8 ms	852 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
int n, rt[N], sz[N];
 
int root(int x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
 
int arr1[N], arr2[N];
 
bool queryy(vector<int> a, vector<int> b){
	for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
	for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
	return query(a.size(), b.size(), arr1, arr2);
}
 
void merge(int x, int y){
	x = root(x), y = root(y);
	assert(x != y);
	if(sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y];
	rt[y] = x;
}
 
void solvee(vector<int> a, vector<int> b){// conected component
	int le = 0, ri = b.size() - 1;
	while(le < ri){
		int mid = (le + ri) >> 1;
		vector<int> temp;
		for(int i = 0; i <= mid; i++) temp.pb(a[i]);
		if(!queryy(temp, b)) le = mid + 1;
		else ri = mid;
	}
	//int val1 = a[le], tempo = (le >> indd) ^ 1;
	int val1 = a[le];
	le = 0, ri = b.size() - 1;
	while(le < ri){
		int mid = (le + ri) >> 1;
		vector<int> temp;
		for(int i = 0; i <= mid; i++) temp.pb(b[i]);
		if(!queryy(a, temp)) le = mid + 1;
		else ri = mid;
	}
	int val2 = b[le];
	merge(val1, val2);
	setRoad(val1, val2);
}
 
int ind[N];
 
mt19937 rng(7405);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
    return abs(temp) + l;
}
 
bool ck1[N], ck2[N];
 
void run(int N){
	n = N;
	for(int i = 1; i <= n; i++){
		rt[i] = i;
		sz[i] = 1;
	}
	int temp = n - 1;
	while(temp--){
		vector<int> v;
		for(int i = 1; i <= n; i++) if(root(i) == i) v.pb(i);
		for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
		vector<int> a, b;
		int indd = 7;
		for(int i = 6; i >= 0; i--){
           a.clear(), b.clear();
			for(int j = 1; j <= n; j++){
				if(ind[root(j)] & (1LL << i)) a.pb(j);
				else b.pb(j);
			}
			if(queryy(a, b)){
				indd = i;
				break;
			}
		}
      assert(indd >= 0 && indd <= 6);
		a.clear(), b.clear();
		for(int i = 0; i < v.size(); i++){
			if(i & (1LL << indd)) a.pb(i);
			else b.pb(i);
		}
      vector<int> temp1, temp2;
      for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
			for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
			for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
			for(int i = 1; i <= n; i++){
				if(ck1[root(i)]) temp1.pb(i);
				if(ck2[root(i)]) temp2.pb(i);
			}
      assert(queryy(temp1, temp2));
		int le = 0, ri = a.size() - 1;// first position to be correct
		while(le < ri){
			int mid = (le + ri) >> 1;
			vector<int> temp1, temp2;
			for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
			for(int i = 0; i <= mid; i++) ck1[a[i]] = 1;
			for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
			for(int i = 1; i <= n; i++){
				if(ck1[root(i)]) temp1.pb(i);
				if(ck2[root(i)]) temp2.pb(i);
			}
			//for(int i = 0; i <= mid; i++) temp.pb(a[i]);
			if(!queryy(temp1, temp2)) le = mid + 1;
			else ri = mid;
		}
		vector<int> c;
		for(auto it : b){
			int x = (it >> indd), y = (a[le] >> indd);
			if(x == (y ^ 1)) c.pb(it);
		}
		//b = c;
		//int val1 = a[le], tempo = (le >> indd) ^ 1;
		int val1 = a[le];
		le = 0, ri = b.size() - 1;
		while(le < ri){
			int mid = (le + ri) >> 1;
			vector<int> temp1, temp2;
			for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
			for(int i = 0; i <= mid; i++) ck2[b[i]] = 1;
			for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
			for(int i = 1; i <= n; i++){
				if(ck1[root(i)]) temp1.pb(i);
				if(ck2[root(i)]) temp2.pb(i);
			}
			//for(int i = 0; i <= mid; i++) temp.pb(b[i]);
			if(!queryy(temp1, temp2)) le = mid + 1;
			else ri = mid;
		}
		int val2 = b[ri];
		vector<int> v1, v2;
		for(int i = 1; i <= n; i++){
			if(root(i) == val1) v1.pb(i);
			if(root(i) == val2) v2.pb(i);
		}
        //assert(queryy(v1, v2));
		solvee(v1, v2);
	}
}
 
/*
void process(){
 
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message (stderr)

icc.cpp:17:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   17 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
icc.cpp: In function 'bool queryy(std::vector<int>, std::vector<int>)':
icc.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
      |                 ~~^~~~~~~~~~
icc.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
      |                 ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
      |                  ~~^~~~~~~~~~
icc.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0; i < v.size(); i++){
      |                  ~~^~~~~~~~~~
icc.cpp:108:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
      |                   ~~^~~~~~~~~~
icc.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |    for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
      |                   ~~^~~~~~~~~~
icc.cpp:121:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
      |                   ~~^~~~~~~~~~
icc.cpp:144:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |    for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
      |                   ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10