oj.uz

Submission #700959

# Submission time Handle Problem Language Result Execution time Memory
700959 2023-02-19T13:54:55 Z beaconmc ICC (CEOI16_icc) C++14
0 / 100
 1 ms 468 KB 
#include "icc.h"
#include <bits/stdc++.h>


typedef int ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll a_imp, b_imp;


ll n = 0;

ll cc[200];
int find(ll a){
	while (cc[a] != a){
		cc[a] = cc[cc[a]];
		a = cc[a];
	}
	return a;
}

// bool query(ll a, ll b, vector<ll> aa, vector<ll> bb){

// 	bool left = 0, right = 0;
// 	bool ll=0, rr = 0;
// 	for (auto&i : aa) if (i==a_imp) left = 1;
// 	for (auto&i : bb) if (i==b_imp) right = 1;

// 	for (auto&i : aa) if (i==b_imp) ll = 1;
// 	for (auto&i : bb) if (i==a_imp) rr = 1;



// 	return (left&right) | (ll & rr);
// }


void unite(ll a, ll b){
	cc[find(a)] = find(b);
}

bool unpackquery(vector<ll> a, vector<ll> b){
	vector<vector<ll>> unpacked(n+1);
	FOR(i,1,n+1) unpacked[find(i)].push_back(i);

	vector<ll> aa, bb;
	for (auto&i : a){
		for (auto&k : unpacked[i]){
			aa.push_back(k);
		}
	}
	for (auto&i : b){
		for (auto&k : unpacked[i]){
			bb.push_back(k);
		}
	}
	return query(aa.size(), bb.size(), aa.data(), bb.data());
}
bool realquery(vector<ll> a, vector<ll> b){

	return query(a.size(), b.size(), a.data(), b.data());
}


void uniquesolve(vector<ll> a){
	ll xored = 0;

	FOR(i,0,ceil(log2(a.size()+1))){
		vector<ll> one;
		vector<ll> zero;
		FOR(j,0,a.size()){
			if ((j & (1<<i)) != 0) one.push_back(a[j]);
			else zero.push_back(a[j]);
		}

		xored |= (1<<i) * realquery(one, zero);
	}
	//cout << xored << endl;

	ll xor2 = 0;

	FOR(i,0,ceil(log2(a.size()+1))){
		vector<ll> one;
		vector<ll> anti;

		FOR(j,0,a.size()){
			if ((j & (1<<i)) != 0) one.push_back(j);
		}
		for (auto&j : one){
			if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			anti.push_back(xored ^ j);
		}

		FOR(j,0,one.size()) one[j] = a[one[j]];
		FOR(j,0,anti.size()) anti[j] = a[anti[j]];


		xor2 |= (1<<i) * realquery(one, anti);

	}
	//cout << a[xor2] <<" " << a[xored^xor2] <<  endl;
	setRoad(a[xor2], a[xored^xor2]);
	unite(a[xor2], a[xored^xor2]);

}

void solve(vector<ll> a){
	vector<vector<ll>> unpacked(n+1);
	FOR(i,1,n+1) unpacked[find(i)].push_back(i);

	set<ll> idk;
	for (auto&i : a) idk.insert(find(i));

	a.clear();
    for (auto&i : idk) a.push_back(i);
	ll xored = 0;


	FOR(i,0,ceil(log2(a.size()+1))){
		vector<ll> one;
		vector<ll> zero;
		FOR(j,0,a.size()){
			if ((j & (1<<i)) != 0) one.push_back(a[j]);
			else zero.push_back(a[j]);
		}

		xored |= (1<<i) * unpackquery(one, zero);
	}
	//cout << xored << endl;

	ll xor2 = 0;

	FOR(i,0,ceil(log2(a.size()+1))){
		vector<ll> one;
		vector<ll> anti;

		FOR(j,0,a.size()){
			if ((j & (1<<i)) != 0) one.push_back(j);
		}
		for (auto&j : one){
			if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			anti.push_back(xored ^ j);
		}

		FOR(j,0,one.size()) one[j] = a[one[j]];
		FOR(j,0,anti.size()) anti[j] = a[anti[j]];


		xor2 |= (1<<i) * unpackquery(one, anti);

	}
	vector<ll> news;
	//cout << a[xor2] << " " << a[xored^xor2] << endl;

	for (auto&i : unpacked[find(a[xor2])]){
		//cout << i << " ";
		news.push_back(i);
	}
	for (auto&i : unpacked[find(a[xored^xor2])]){
		//cout << i <<" ";
		news.push_back(i);
	}
	//cout << "SUS" << endl;
	//cout << news.size() << endl;
	uniquesolve(news);
}



void run(int N){
	n = N;
	FOR(i,0,200) cc[i] = i;
	vector<ll> sus(n);
	FOR(i,0,n) sus[i] = i+1;
	FOR(i,0,n-1){
		solve(sus);
	}
}

Compilation message

icc.cpp: In function 'void uniquesolve(std::vector<int>)':
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   77 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:77:3: note: in expansion of macro 'FOR'
   77 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   92 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:92:3: note: in expansion of macro 'FOR'
   92 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:96:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |    if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |        ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  100 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |       ~~~~~~~~~~~~~~               
icc.cpp:100:3: note: in expansion of macro 'FOR'
  100 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |   ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  101 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |       ~~~~~~~~~~~~~~~              
icc.cpp:101:3: note: in expansion of macro 'FOR'
  101 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |   ^~~
icc.cpp: In function 'void solve(std::vector<int>)':
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  128 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:128:3: note: in expansion of macro 'FOR'
  128 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  143 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:143:3: note: in expansion of macro 'FOR'
  143 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:147:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |    if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |        ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  151 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |       ~~~~~~~~~~~~~~               
icc.cpp:151:3: note: in expansion of macro 'FOR'
  151 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |   ^~~
icc.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
  152 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |       ~~~~~~~~~~~~~~~              
icc.cpp:152:3: note: in expansion of macro 'FOR'
  152 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |   ^~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 424 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -