Submission #19549018

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> pii;
#define mp make_pair
#define fi first
#define se second

int n,cnt[4],f[3],g[3],_g[3],_cnt[4];
map<int,bool> p;
map<int,array<int,3>> q;

int getid(array<int,3> a) {
	for(int i=0;i<3;i++) if(a[i]) return i;
	return 3;
}

array<int,3> getarr(int id) {
	return {id==0,id==1,id==2};
}

int main() {
#ifdef LOCAL
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1,x,y;i<=n;i++) {
		cin>>x>>y;
		p[y]^=1;q[x][y%3]^=1;
	}
	for(auto t:p) if(t.se) ++f[t.fi%3];
	bool b=0;
	for(auto t:q) {
		auto a=t.se;
		if(a[0]+a[1]+a[2]>=2) a[0]=1-a[0],a[1]=1-a[1],a[2]=1-a[2],b^=1;
		++_cnt[getid(a)];_g[0]+=a[0];_g[1]+=a[1];_g[2]+=a[2];
	}
	int ans=1e9;
	for(int s=0;s<16;s++)
		if(__builtin_parity(s)==b) {
			memcpy(cnt,_cnt,sizeof(cnt));
			memcpy(g,_g,sizeof(g));
			bool fl=1;
			for(int i=0;i<4;i++)
				if(s>>i&1) {
					if(!cnt[i]) { fl=0;break; }
					--cnt[i];
					auto tmp=getarr(i);
					for(int j=0;j<3;j++) g[j]+=1-2*tmp[j];
				}
			if(!fl) continue;
			int val=max(f[0],g[0])+max(f[1],g[1])+max(f[2],g[2]);
			//if(s==8) cerr<<val;
			ans=min(ans,val);
			for(int i=0;i<3;i++)
				if(g[i]>f[i]) {
					int tmp=min({g[i]-f[i],cnt[i],f[0]-g[0],f[1]-g[1],f[2]-g[2]});
					if(tmp&1) --tmp;
					ans=min(ans,val-tmp);break;
				}
		}
	cout<<ans;
	return 0;
}

Submission Info

Judge Result