| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 700968 | beaconmc | ICC (CEOI16_icc) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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){
set<ll> sus;
for (auto&i : aa) sus.insert(i);
for (auto&i : bb) sus.insert(i);
if (sus.size() != aa.size() + bb.size()){
cout << a <<" " << b << endl;
for (auto&i : aa) cout << i << " ";
cout << endl;
for (auto&i : bb) cout << i << " ";
cout << endl;
cout << "UWU" << endl;
}
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, bb);
}
bool realquery(vector<ll> a, vector<ll> b){
return query(a.size(), b.size(), a, b);
}
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;
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;
a_imp = 5;
b_imp = 4;
solve(sus);
a_imp = 2;
b_imp = 3;
solve(sus);
a_imp = 10;
b_imp = 5;
solve(sus);
a_imp = 10;
b_imp = 8;
solve(sus);
a_imp = 1;
b_imp = 5;
solve(sus);
}
int main(){
run(10);
}