This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Memory2_lib.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int arr[3][110];
int l[110], r[110];
pii ans[110];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void ch(int num){
if(arr[num][1]==arr[num][2])
pq.push(mp(arr[num][1], num));
}
void f(int NUM){
if(!NUM)return;
int temp=pq.top().F;
vector<pii> t;
while(pq.size()){
if(pq.top().F==temp){
t.pb(pq.top());
pq.pop();
}
else break;
}
if(NUM==1){
ans[t[0].F]=mp(t[0].S, t[1].S);
return;
}
if(NUM==2&&t.size()==4){
int tt=Flip(t[0].S, t[2].S);
ans[tt]=mp(t[0].S, t[2].S);
tt=Flip(t[1].S, t[3].S);
ans[tt]=mp(t[1].S, t[3].S);
return;
}
if(t.size()==2){
ans[t[0].F]=mp(t[0].S, t[1].S);
l[r[t[0].S]]=l[t[0].S];
r[l[t[0].S]]=r[t[0].S];
l[r[t[1].S]]=l[t[1].S];
r[l[t[1].S]]=r[t[1].S];
int tt=Flip(l[t[0].S], r[t[0].S]);
arr[l[t[0].S]][1]=tt;
arr[r[t[0].S]][2]=tt;
tt=Flip(l[t[1].S], r[t[1].S]);
arr[l[t[1].S]][1]=tt;
arr[r[t[1].S]][2]=tt;
ch(l[t[0].S]);
ch(r[t[0].S]);
ch(l[t[1].S]);
ch(r[t[1].S]);
}
if(t.size()==3){
int num=0, now=t[0].S;
for(; num<=3; num++){
if(now!=t[num].S)break;
now=r[now];
}
if(num==2){
swap(t[0], t[1]);
swap(t[1], t[2]);
}
else{
swap(t[1], t[2]);
}
ans[t[0].F]=mp(t[0].S, t[1].S);
l[r[t[0].S]]=l[t[0].S];
r[l[t[0].S]]=r[t[0].S];
l[r[t[1].S]]=l[t[1].S];
r[l[t[1].S]]=r[t[1].S];
int tt=Flip(l[t[0].S], r[t[0].S]);
arr[l[t[0].S]][1]=tt;
arr[r[t[0].S]][2]=tt;
tt=Flip(l[t[1].S], r[t[1].S]);
arr[l[t[1].S]][1]=tt;
arr[r[t[1].S]][2]=tt;
ch(l[t[0].S]);
ch(l[t[1].S]);
ch(r[t[1].S]);
}
if(t.size()==4){
int num=0, now=t[0].S;
for(; num<=4; num++){
if(now!=t[num].S)break;
now=r[now];
}
if(num==1){
swap(t[0], t[2]);
swap(t[1], t[3]);
}
if(num==2){
swap(t[1], t[3]);
}
if(num==4){
swap(t[0], t[1]);
swap(t[1], t[2]);
}
ans[t[0].F]=mp(t[0].S, t[1].S);
l[r[t[1].S]]=l[t[0].S];
r[l[t[0].S]]=r[t[1].S];
int tt=Flip(l[t[0].S], r[t[1].S]);
arr[l[t[0].S]][1]=tt;
arr[r[t[1].S]][2]=tt;
ch(l[t[0].S]);
ch(r[t[1].S]);
}
}
void Solve(int T, int n){
n*=2;
for(int i=0; i<n; i++){
r[i]=(i+1)%n;
l[(i+1)%n]=i;
}
for(int i=0; i<n; i++){
int t1=Flip(i, (i+1)%n);
arr[i][1]=t1;
arr[(i+1)%n][2]=t1;
}
for(int i=0; i<n; i++){
ch(i);
}
f(n/2);
for(int i=0; i<n/2; i++){
Answer(ans[i].F, ans[i].S, i);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |