| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1316931 | vlomaczk | 카멜레온의 사랑 (JOI20_chameleon) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
#include "chameleon.h"
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
set<pair<int, int>> Sa;
void Ans(int x, int y) {
if(x>y) swap(x,y);
if(x==y) return;
Sa.insert({x,y});
}
void Finish() {
for(auto[a,b] : Sa) Answer(a,b);
}
void Solve(int N) {
vector<set<int>> V(2*N+1);
vector<vector<int>> G(2*N+1), g(2*N+1);
for(int i=1; i<=2*N; ++i) {
vector<int> sets(2);
vector<int> vis(2*N+1);
queue<pair<int, int>> Q;
for(int x=1; x<i; ++x) {
Q.push({x,0});
while(Q.size()) {
auto[v,c] = Q.front(); Q.pop();
sets[c].push_back(v);
vis[v] = 1;
for(auto u : g[v]) {
if(vis[u]) continue;
Q.push({u,c^1});
}
}
}
for(int k=0; k<2; ++k) {
vector<int> q = sets[k];
q.push_back(i);
int Q = Query(q);
int start = 0;
while(q.size() - Q > 0) {
int lo = 0;
int hi = sets[k].size() - 1;
while(lo < hi) {
int mid=(lo+hi)/2;
vector<int> p; p.push_back(i);
for(int j=start; j<=mid; ++j) p.push_back(sets[k][j]);
if(p.size() - Query(p) > 0) hi = mid;
else lo = mid+1;
}
G[i].push_back(sets[k][lo]);
g[i].push_back(sets[k][lo]);
G[sets[k][lo]].push_back(i);
start = lo+1;
while(q.size()) q.pop_back();
for(int j=start; j<sets[k].size(); ++j) q.push_back(sets[k][j]);
q.push_back(i);
Q = Query(q);
}
}
}
for(int i=1; i<=2*N; ++i) for(auto x : G[i]) V[i].insert(x);
for(int i=1; i<=2*N; ++i) {
if(V[i].size()==1) Ans(i,*V[i].begin());
else {
vector<int> v;
for(auto x : G[i]) v.push_back(x);
for(int j=0; j<3; ++j) {
vector<int> p = {i};
for(int x=0; x<3; ++x) if(x!=j) p.push_back(v[x]);
if(Query(p)==1) {
V[i].erase(v[j]);
V[v[j]].erase(i);
}
}
}
}
for(int i=1; i<=2*N; ++i) {
if(V[i].size()==1) Ans(i,*V[i].begin());
}
Finish();
}