oj.uz

Submission #700962

# Submission time Handle Problem Language Result Execution time Memory
700962 2023-02-19T14:09:51 Z beaconmc ICC (CEOI16_icc) C++14
0 / 100
 11 ms 512 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){
	if (a.size() == 0 || b.size() == 0) return 0;
	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){
	if (a.size() == 0 || b.size() == 0) return 0;

	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 ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			if ((xored ^ j) == j) continue;
			if ((j & (1<<i)) != 0) one.push_back(j);
		}
		for (auto&j : one){
			if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			if ((xored ^ j) == 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 ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			if ((xored ^ j) == j) continue;
			if ((j & (1<<i)) != 0) one.push_back(j);
		}
		for (auto&j : one){
			if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
			if ((xored ^ j) == 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++)
......
   79 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:79:3: note: in expansion of macro 'FOR'
   79 |   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++)
......
   94 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:94:3: note: in expansion of macro 'FOR'
   94 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:95:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |    if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |        ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:100:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    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++)
......
  105 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |       ~~~~~~~~~~~~~~               
icc.cpp:105:3: note: in expansion of macro 'FOR'
  105 |   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++)
......
  106 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |       ~~~~~~~~~~~~~~~              
icc.cpp:106:3: note: in expansion of macro 'FOR'
  106 |   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++)
......
  133 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:133:3: note: in expansion of macro 'FOR'
  133 |   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++)
......
  148 |   FOR(j,0,a.size()){
      |       ~~~~~~~~~~~~                 
icc.cpp:148:3: note: in expansion of macro 'FOR'
  148 |   FOR(j,0,a.size()){
      |   ^~~
icc.cpp:149:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if ((xored ^ j) >= a.size() || j < (xored^j)) continue;
      |        ~~~~~~~~~~~~^~~~~~~~~~~
icc.cpp:154:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |    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++)
......
  159 |   FOR(j,0,one.size()) one[j] = a[one[j]];
      |       ~~~~~~~~~~~~~~               
icc.cpp:159:3: note: in expansion of macro 'FOR'
  159 |   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++)
......
  160 |   FOR(j,0,anti.size()) anti[j] = a[anti[j]];
      |       ~~~~~~~~~~~~~~~              
icc.cpp:160:3: note: in expansion of macro 'FOR'
  160 |   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 Wrong road!
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 508 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 512 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 468 KB Wrong road!
2 Halted 0 ms 0 KB -