1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include "osalib.h"

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
int pd[1100][1100],cnt,father[1100000],f[1100][1100],len;
unsigned long long wd[1100][1100],w[1100000],wfather[1100000],all,wr[1100][1100];
int n,m;
int findfather(int k1){
	if (father[k1]==k1) return k1;
	int where=findfather(father[k1]);
	wfather[k1]^=wfather[father[k1]]; father[k1]=where;
	return where;
}
void link(int k1,int k2,unsigned long long w){
	int f1=findfather(k1),f2=findfather(k2);
	if (f1==f2) return;
	//cout<<"link "<<k1<<" "<<k2<<" "<<w<<" "<<f1<<" "<<f2<<endl;
	w^=wfather[k1]^wfather[k2]; father[f1]=f2; wfather[f1]=w;
}
void link(int x1,int y1,int x2,int y2,unsigned long long w){
	link(f[x1][y1],f[x2][y2],w);
}
unsigned long long queryw(int x,int y){
	int k1=f[x][y]; findfather(k1); return wfather[k1];
}
void NowaWyspa(int _n, int _m, char **board){
	memset(pd,0xff,sizeof pd); n=_n; m=_m;
	//cout<<"asd "<<n<<" "<<m<<endl;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (board[i][j]=='K') pd[i+1][j+1]=++cnt;
			else if (board[i][j]=='W') pd[i+1][j+1]=0;
	/*for (int i=0;i<n;i++){
		for (int j=0;j<m;j++) cout<<pd[i+1][j+1]<<" "; cout<<endl;}
	for (int i=0;i<n;i++){
		for (int j=0;j<m;j++) cout<<board[i][j]; cout<<endl;}*/
	len=cnt; cnt=0;
	for (int i=1;i<=len;i++){
		for (int j=0;j<64;j++) if (rand()%2==0) w[i]^=(1ull<<j);
		//w[i]=(1<<i-1);
	}
	for (int i=1;i<=len;i++) all^=w[i];
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (pd[i][j]>0) wr[i][j]=(wr[i][j-1]^w[pd[i][j]]);
			else wr[i][j]=wr[i][j-1];
	//for (int i=1;i<=n;i++){
	//	for (int j=1;j<=m;j++) cout<<wr[i][j]<<" "; cout<<endl;}
	for (int i=1;i<=n+1;i++)
		for (int j=1;j<=m+1;j++)
			f[i][j]=++cnt;
	for (int i=1;i<=cnt;i++) father[i]=i,wfather[i]=0;
	for (int i=1;i<=m;i++) link(1,i,1,i+1,0),link(n+1,i,n+1,i+1,0);
	for (int i=1;i<=n;i++) link(i,1,i+1,1,0),link(i,m+1,i+1,m+1,wr[i][m]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (pd[i][j]==0){
				link(i,j,i,j+1,wd[i-1][j]);
				link(i,j+1,i+1,j+1,wr[i][j]);
				link(i+1,j+1,i+1,j,wd[i][j]);
				link(i+1,j,i,j,wr[i][j-1]);
			}
}
int NowaWarownia(int r, int c){
	//cout<<"insert "<<r<<" "<<c<<endl;
	int A[4]; unsigned long long we[4];
	assert(pd[r][c]=-1);
	A[0]=f[r][c]; A[1]=f[r][c+1]; A[2]=f[r+1][c+1]; A[3]=f[r+1][c];
	we[0]=wd[r-1][c]; we[1]=wr[r][c]; we[2]=wd[r][c]; we[3]=wr[r][c-1];
	/*for (int i=0;i<4;i++) cout<<we[i]<<" "; cout<<endl;
	cout<<"asd pd"<<endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) cout<<pd[i][j]<<" "; cout<<endl;
	}
	cout<<"asd wr"<<endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) cout<<wr[i][j]<<" "; cout<<endl;
	}
	cout<<"asd wd"<<endl;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) cout<<wd[i][j]<<" "; cout<<endl;
	}*/
	for (int i=0;i<4;i++)
		for (int j=0;j<4;j++)
			if (i!=j){
				if (findfather(A[i])!=findfather(A[j])) continue;
				unsigned long long now=wfather[A[i]]^wfather[A[j]];
				//cout<<"asd "<<A[i]<<" "<<A[j]<<" "<<i<<" "<<j<<" "<<now<<endl;
				for (int k=i;k!=j;k=(k+1)%4) now^=we[k];
				//cout<<now<<" "<<all<<endl;
				if (now!=0&&now!=all) return 0;
			}
	pd[r][c]=0;
	for (int i=0;i<4;i++)
		link(A[i],A[(i+1)%4],we[i]);
	//cout<<"true"<<endl;
	return 1;
}
void PrzeniesOsade(int r1, int c1, int r2, int c2) {
	//cout<<"move "<<r1<<" "<<c1<<" "<<r2<<" "<<c2<<endl;
	assert(1<=r1&&r1<=n&&1<=c1&&c1<=m);
	assert(1<=r2&&r2<=n&&1<=c2&&c2<=m);
	assert(pd[r1][c1]>0&&pd[r2][c2]==-1);
	assert(abs(r1-r2)+abs(c1-c2)==1);
	int where=pd[r1][c1];
	if (r1==r2){
		if (c1==c2+1){
			wr[r2][c2]^=w[where];
		} else {
			wr[r1][c1]^=w[where];
		}
	} else if (r1==r2+1){
		wd[r2][c2]^=w[where];
	} else {
		wd[r1][c1]^=w[where];
	}
	pd[r1][c1]=-1; pd[r2][c2]=where;
}