Submission #32826656

---

Source Code Expand

/*
Author: cnyz
----------------
Looking! The blitz loop this planet to search way.
Only my RAILGUN can shoot it. 今すぐ
*/
#include<bits/stdc++.h>
using namespace std;
using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;
#define fi first
#define se second
#define gc getchar
#define pb push_back
#define emp emplace_back
#define sz(a) (int)a.size()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
int read() {
    int x=0;char ch=gc();
    while(!isdigit(ch)) ch=gc();
    while(isdigit(ch)) x=10*x+ch-'0',ch=gc();
    return x;
}
void chkmax(int &x,int y) {if(x<y) x=y;}
const int N=1e5;
int n,a[4][N+10],val[N+10],cnt1,cnt0;
void run() {puts("No"),exit(0);}
int bit[N+10];
void add(int x) {for(;x<=n;x+=x&(-x)) bit[x]++;}
int ask(int x) {int ret=0;for(;x;x-=x&(-x)) ret+=bit[x];return ret;}
void clr() {memset(bit,0,sizeof bit);}
int main() {
    n=read();
    FOR(i,1,3) FOR(j,1,n) a[i][j]=read();
    FOR(i,1,n) {
        if(a[1][i]%3==0) {
            if(a[2][i]==a[1][i]-1&&a[3][i]==a[1][i]-2) val[i]=-a[1][i]/3;
            else run();
        }
        else if(a[3][i]%3==0) {
            if(a[2][i]==a[3][i]-1&&a[1][i]==a[3][i]-2) val[i]=a[3][i]/3;
            else run();
        }
        else run();
    }
    for(int i=1;i<=n;i+=2) {
        if(val[i]<0) cnt1^=1,val[i]=-val[i];
        if(val[i]%2==0) run();
    }
    for(int i=2;i<=n;i+=2) {
        if(val[i]<0) cnt0^=1,val[i]=-val[i];
        if(val[i]%2==1) run();
    }
    for(int i=1;i<=n;i+=2) {
        cnt0^=((ask(n)-ask(val[i]))&1);
        add(val[i]);
    }clr();
    for(int i=2;i<=n;i+=2) {
        cnt1^=((ask(n)-ask(val[i]))&1);
        add(val[i]);
    }
    if(cnt0||cnt1) run();
    puts("Yes");
}

Submission Info

Judge Result