QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#234957#7636. Fair Electionsucup-team1004WA 554ms4248kbC++142.8kb2023-11-02 07:19:182023-11-02 07:19:18

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 07:19:18]
  • 评测
  • 测评结果:WA
  • 用时:554ms
  • 内存:4248kb
  • [2023-11-02 07:19:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T> &x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int i=1,len=x.size();i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<endl;
}
template<typename T,typename ... S>
void debug(T x,S...y){
	cerr<<x<<' ',debug(y...);
}
const int N=1e4+10;
int n,a[3],p[N][3];
struct seg{
	int l,r;
	seg(int x=1,int y=0):l(x),r(y){}
	bool empty()const{
		return l>r;
	}
	seg operator | (const seg &x)const{
		if(empty())return x;
		if(x.empty())return *this;
		return seg(min(l,x.l),max(r,x.r));
	}
	seg operator |= (const seg &x){
		return *this=*this|x;
	}
	seg operator & (const seg &x)const{
		if(empty())return *this;
		if(x.empty())return x;
		return seg(max(l,x.l),min(r,x.r));
	}
	friend ostream& operator << (ostream &out,const seg &x){
		return out<<'('<<x.l<<','<<x.r<<')';
	}
	seg operator - (const seg &x)const{
		if(x.empty()||empty())return *this;
		if(x.l>r||x.r<l)return *this;
		else if(r<=x.r)return seg(l,x.l-1);
		else if(x.l<=l)return seg(x.r+1,r);
		else{
			cout<<*this<<' '<<x<<endl;
			return 0;
		}
	}
	seg operator - (const int &x)const{
		return seg(l-x,r-x);
	}
}f[2][N][3];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++){
			cin>>p[i][j],p[i][j]--; 
		}
	}
	int now=0,las=1;
	for(a[0]=0;a[0]<=n;a[0]++){
		for(a[1]=0;a[0]+a[1]<=n;a[1]++){
			a[2]=n-a[0]-a[1];
			int ans=0;
			for(int i=1;i<3;i++)if(a[ans]<a[i])ans=i;
			// debug(f[n+1][a[0]][ans],seg(a[1],a[1]),f[n+1][a[0]][ans]|seg(a[1],a[1]));
			f[now][a[0]][ans]|=seg(a[1],a[1]);
		}
		// for(int j=0;j<3;j++){
		// 	debug(n+1,a[0],j,f[n+1][a[0]][j]);
		// }
	}
	for(int i=n;i>=1;i--){
		swap(now,las);
		for(int j=0;j<3;j++){
			for(int k=0;k<i;k++)f[now][k][j]=seg();
		}
		for(int j=0;j<3;j++){
			if(p[i][j]==0){
				for(int k=0;k<i;k++){
					// debug(0,i,j,k,f[i+1][k+1][0]&seg(0,i-1-k),f[i][k][1],f[i][k][2]);
					f[now][k][0]|=(f[las][k+1][0]&seg(0,i-1-k))-(f[now][k][1]|f[now][k][2]);
				}
			}else if(p[i][j]==1){
				for(int k=0;k<i;k++){
					// debug(1,i,j,k,(f[i+1][k][1]-1)&seg(0,i-1-k),f[i][k][0],f[i][k][2]);
					f[now][k][1]|=((f[las][k][1]-1)&seg(0,i-1-k))-(f[now][k][0]|f[now][k][2]);
				}
			}else{
				for(int k=0;k<i;k++){
					// debug(2,i,j,k,f[i+1][k][2]&seg(0,i-1-k),f[i][k][0],f[i][k][1]);
					f[now][k][2]|=(f[las][k][2]&seg(0,i-1-k))-(f[now][k][0]|f[now][k][1]);
				}
			}
		}
		// for(int j=0;j<3;j++){
		// 	debug(n+1,a[0],j,f[n+1][a[0]][j]);
		// }
	}
	for(int j=0;j<3;j++){
		if(!f[now][0][j].empty())cout<<j+1<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4128kb

input:

3
3 2 1
1 2 3
2 1 3

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4060kb

input:

5
1 2 3
2 3 1
1 3 2
3 1 2
2 1 3

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

5
1 2 3
3 2 1
1 2 3
1 2 3
3 2 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

5
3 2 1
3 1 2
2 3 1
1 2 3
2 1 3

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 0ms
memory: 4140kb

input:

5
3 2 1
3 2 1
1 3 2
1 3 2
3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

5
3 2 1
3 1 2
1 2 3
1 3 2
1 3 2

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

20
1 2 3
2 3 1
1 3 2
3 1 2
2 1 3
1 2 3
3 2 1
1 2 3
1 2 3
3 2 1
3 2 1
3 1 2
2 3 1
1 2 3
2 1 3
3 2 1
3 2 1
1 3 2
1 3 2
3 2 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 4136kb

input:

20
3 2 1
3 1 2
1 2 3
1 3 2
1 3 2
1 2 3
3 1 2
1 3 2
3 2 1
1 3 2
2 1 3
3 1 2
2 3 1
2 1 3
2 3 1
3 1 2
3 1 2
2 1 3
3 1 2
1 2 3

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 4136kb

input:

20
1 2 3
2 3 1
2 1 3
2 1 3
1 3 2
3 1 2
2 3 1
1 3 2
3 1 2
1 2 3
1 2 3
3 2 1
3 1 2
1 2 3
3 2 1
1 2 3
2 3 1
3 1 2
3 2 1
3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #10:

score: 0
Accepted
time: 0ms
memory: 4064kb

input:

20
3 1 2
3 2 1
1 2 3
1 3 2
1 3 2
2 3 1
1 3 2
2 3 1
1 2 3
3 2 1
1 2 3
3 2 1
1 2 3
1 2 3
3 2 1
2 3 1
2 3 1
1 2 3
2 1 3
2 1 3

output:

1

result:

ok 1 number(s): "1"

Test #11:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

20
2 1 3
2 1 3
3 1 2
3 2 1
2 1 3
1 2 3
2 3 1
3 1 2
3 1 2
2 3 1
3 2 1
1 3 2
2 1 3
2 1 3
1 2 3
2 3 1
2 3 1
3 2 1
2 1 3
1 3 2

output:

2

result:

ok 1 number(s): "2"

Test #12:

score: -100
Wrong Answer
time: 554ms
memory: 4248kb

input:

10000
1 2 3
2 3 1
1 3 2
3 1 2
2 1 3
1 2 3
3 2 1
1 2 3
1 2 3
3 2 1
3 2 1
3 1 2
2 3 1
1 2 3
2 1 3
3 2 1
3 2 1
1 3 2
1 3 2
3 2 1
3 2 1
3 1 2
1 2 3
1 3 2
1 3 2
1 2 3
3 1 2
1 3 2
3 2 1
1 3 2
2 1 3
3 1 2
2 3 1
2 1 3
2 3 1
3 1 2
3 1 2
2 1 3
3 1 2
1 2 3
1 2 3
2 3 1
2 1 3
2 1 3
1 3 2
3 1 2
2 3 1
1 3 2
3 1 2
...

output:

(1986,4027) (2010,2011)
(1980,4026) (2009,2010)
(1980,4025) (2008,2009)
(1966,4024) (2007,2008)
(1958,4023) (2006,2007)
(1958,4022) (2005,2006)
(1,2010) (1954,2003)
(0,2011) (1954,2003)
(0,4003) (1,1403)
(0,4002) (1,1403)
(0,4001) (1,1403)
(1954,4005) (2008,2008)
(0,3998) (1,1539)
(1974,3959) (1976,...

result:

wrong output format Expected integer, but "(1986,4027)" found