QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234957 | #7636. Fair Elections | ucup-team1004 | WA | 554ms | 4248kb | C++14 | 2.8kb | 2023-11-02 07:19:18 | 2023-11-02 07:19:18 |
Judging History
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