Submission #19549158


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=1e9;
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;
		//cerr<<a[0]<<' '<<a[1]<<' '<<a[2]<<'\n';
		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];
	}
	//cerr<<f[0]<<' '<<f[1]<<' '<<f[2]<<'\n';
	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==0) 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],i==0?inf:f[0]-g[0],i==1?inf:f[1]-g[1],i==2?inf:f[2]-g[2]});
					if((tmp&1)&&min({i==0?inf:f[0]-g[0],i==1?inf:f[1]-g[1],i==2?inf:f[2]-g[2]})==tmp) --tmp;
					ans=min(ans,val-tmp);break;
				}
		}
	cout<<ans;
	return 0;
}

Submission Info

Submission Time
Task C - Flipper
User newbie314159
Language C++ (GCC 9.2.1)
Score 1300
Code Size 1692 Byte
Status AC
Exec Time 66 ms
Memory 9568 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 1
AC × 58
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, example0.txt
Case Name Status Exec Time Memory
000.txt AC 39 ms 5396 KB
001.txt AC 2 ms 3632 KB
002.txt AC 25 ms 4752 KB
003.txt AC 51 ms 6008 KB
004.txt AC 32 ms 5620 KB
005.txt AC 17 ms 4452 KB
006.txt AC 48 ms 6540 KB
007.txt AC 39 ms 5372 KB
008.txt AC 35 ms 6368 KB
009.txt AC 51 ms 7636 KB
010.txt AC 29 ms 5052 KB
011.txt AC 66 ms 9060 KB
012.txt AC 14 ms 4004 KB
013.txt AC 31 ms 5360 KB
014.txt AC 14 ms 4212 KB
015.txt AC 45 ms 6152 KB
016.txt AC 42 ms 6108 KB
017.txt AC 4 ms 3564 KB
018.txt AC 15 ms 3780 KB
019.txt AC 19 ms 4332 KB
020.txt AC 32 ms 5384 KB
021.txt AC 21 ms 4732 KB
022.txt AC 22 ms 5388 KB
023.txt AC 11 ms 4120 KB
024.txt AC 26 ms 5936 KB
025.txt AC 2 ms 3532 KB
026.txt AC 19 ms 3616 KB
027.txt AC 23 ms 3656 KB
028.txt AC 17 ms 3640 KB
029.txt AC 21 ms 3524 KB
030.txt AC 22 ms 3568 KB
031.txt AC 20 ms 3576 KB
032.txt AC 56 ms 8924 KB
033.txt AC 54 ms 8768 KB
034.txt AC 57 ms 8460 KB
035.txt AC 59 ms 9460 KB
036.txt AC 53 ms 9160 KB
037.txt AC 57 ms 9132 KB
038.txt AC 60 ms 9256 KB
039.txt AC 58 ms 9568 KB
040.txt AC 58 ms 8796 KB
041.txt AC 56 ms 9008 KB
042.txt AC 57 ms 9008 KB
043.txt AC 58 ms 9008 KB
044.txt AC 53 ms 8864 KB
045.txt AC 54 ms 8952 KB
046.txt AC 57 ms 9228 KB
047.txt AC 55 ms 9036 KB
048.txt AC 57 ms 9188 KB
049.txt AC 57 ms 8868 KB
050.txt AC 57 ms 9336 KB
051.txt AC 58 ms 8988 KB
052.txt AC 55 ms 8888 KB
053.txt AC 54 ms 9232 KB
054.txt AC 59 ms 8332 KB
055.txt AC 57 ms 8416 KB
056.txt AC 54 ms 8584 KB
example0.txt AC 3 ms 3624 KB