#include <bits/stdc++.h>
#include "chameleon.h"
#include <vector>
#define query Query
#define answer Answer
constexpr int M = 1005;
using namespace std;
vector<vector<int>> sasiedzi(M);
vector<vector<int>> g(M);
vector<vector<int>> g2(M);
int syn[M];
bool uzyte[M];
int kolor[M];
int rep[M];
int sajz[M];
vector<int> spojna[2];
void dfs(int v, int k){
kolor[v] = k;
for(auto i:sasiedzi[v]) if(kolor[i]==0 || kolor[i]==k){
if(k==1) dfs(i, 2);
else dfs(i, 1);
}
}
int ilews(int p, int k, int numer, int koniec){
vector<int> v;
for(int i=p; i<=k; i++) v.push_back(spojna[numer][i-1]);
if(koniec!=0) v.push_back(koniec);
return query(v);
}
int numero;
int bs(int koniec){
int temp1 = ilews(1, spojna[0].size(), 0, 0);
int temp2 = ilews(1, spojna[0].size(), 0, koniec);
//cout<<temp1<<" "<<temp2<<endl;
int numer = 0;
if(temp1 < temp2) numer = 1;
temp1 = ilews(1, spojna[1].size(), 1, 0);
temp2 = ilews(1, spojna[1].size(), 1, koniec);
//cout<<"SPOJNA: "<<numer<<endl;
if(temp1 != temp2 && numer==1) return -1;
int p = 1, k = spojna[numer].size(), mid;
while(p<k){
mid = (p+k)/2;
temp1 = ilews(p, mid, numer, 0);
temp2 = ilews(p, mid, numer, koniec);
if(temp1!=temp2) p = mid + 1;
else k = mid;
}
numero = numer;
return p-1;
}
void Solve(int n) {
for(int i=1; i<=2*n; i++){
int aktKolor = 1;
int wyn = bs(i);
vector<int> doDodania;
//cout<<"wyn: "<<wyn<<endl;
//cout<<endl;
while(wyn!=-1){
sasiedzi[i].push_back(spojna[numero][wyn]);
sasiedzi[spojna[numero][wyn]].push_back(i);
if(kolor[spojna[numero][wyn]] == 1) aktKolor=2;
else if(kolor[spojna[numero][wyn]] == 2) aktKolor=1;
doDodania.push_back(spojna[numero][wyn]);
spojna[numero].erase(spojna[numero].begin() + wyn);
wyn = bs(i);
//cout<<"wyn: "<<wyn<<endl;
}
for(auto j:doDodania){
if(aktKolor==2 && (kolor[j]==2 || kolor[j]==0)) dfs(j, 1);
else if(aktKolor==1 && (kolor[j]==1 || kolor[j]==0)) dfs(j, 2);
}
spojna[0].clear();
spojna[1].clear();
kolor[i] = aktKolor;
for(int j=1; j<=2*n; j++){
if(kolor[j]==1) spojna[0].push_back(j);
if(kolor[j]==2) spojna[1].push_back(j);
}
/*for(int j=1; j<=2*n; j++) cout<<j<<" ";
cout<<endl;
for(int j=1; j<=2*n; j++) cout<<kolor[j]<<" ";
cout<<endl<<endl;
cout<<"S0: ";
for(auto i:spojna[0]) cout<<i<<" ";
cout<<endl;
cout<<"S1: ";
for(auto i:spojna[1]) cout<<i<<" ";
cout<<endl;*/
}
//for(auto i:spojna[0]) cout<<i<<" ";
//cout<<endl;
//for(auto i:spojna[1]) cout<<i<<" ";
//cout<<endl;
//cout<<endl;
//for(int i=1; i<=2*n; i++){
// cout<<i<<": ";
// for(auto j:sasiedzi[i]) cout<<j<<" ";
// cout<<endl;
//}
//cout<<endl;
for(int i=1; i<=n*2; i++){
if(sasiedzi[i].size()!=1){
if(query({i, sasiedzi[i][0], sasiedzi[i][1]})==1) syn[i] = sasiedzi[i][2];
if(query({i, sasiedzi[i][0], sasiedzi[i][2]})==1) syn[i] = sasiedzi[i][1];
if(query({i, sasiedzi[i][2], sasiedzi[i][1]})==1) syn[i] = sasiedzi[i][0];
}
}
for(int i=1; i<=n*2; i++){
if(syn[i]!=0){
g[i].push_back(syn[i]);
g[syn[i]].push_back(i);
}
}
for(int i=1; i<=n*2; i++){
sort(g[i].begin(), g[i].end());
if(syn[i]==0){
if(uzyte[min(i, sasiedzi[i][0])] == 0){
uzyte[min(i, sasiedzi[i][0])] = 1;
answer(i, sasiedzi[i][0]);
}
}
else{
if(g[i][0] == sasiedzi[i][0] && g[i][1] == sasiedzi[i][1]){
if(uzyte[min(i, sasiedzi[i][2])] == 0){
uzyte[min(i, sasiedzi[i][2])] = 1;
answer(i, sasiedzi[i][2]);
}
}
else if(g[i][0] == sasiedzi[i][0] && g[i][1] == sasiedzi[i][2]){
if(uzyte[min(i, sasiedzi[i][1])] == 0){
uzyte[min(i, sasiedzi[i][1])] = 1;
answer(i, sasiedzi[i][1]);
}
}
else if(g[i][0] == sasiedzi[i][1] && g[i][1] == sasiedzi[i][2]){
if(uzyte[min(i, sasiedzi[i][0])] == 0){
uzyte[min(i, sasiedzi[i][0])] = 1;
answer(i, sasiedzi[i][0]);
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
26 ms |
344 KB |
Output is correct |
| 4 |
Correct |
27 ms |
556 KB |
Output is correct |
| 5 |
Correct |
27 ms |
344 KB |
Output is correct |
| 6 |
Correct |
26 ms |
344 KB |
Output is correct |
| 7 |
Correct |
26 ms |
536 KB |
Output is correct |
| 8 |
Correct |
26 ms |
560 KB |
Output is correct |
| 9 |
Correct |
26 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
27 ms |
540 KB |
Wrong Answer [3] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
26 ms |
344 KB |
Output is correct |
| 4 |
Correct |
27 ms |
556 KB |
Output is correct |
| 5 |
Correct |
27 ms |
344 KB |
Output is correct |
| 6 |
Correct |
26 ms |
344 KB |
Output is correct |
| 7 |
Correct |
26 ms |
536 KB |
Output is correct |
| 8 |
Correct |
26 ms |
560 KB |
Output is correct |
| 9 |
Correct |
26 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [1] |
| 12 |
Halted |
0 ms |
0 KB |
- |
