QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#560887 | #8688. Quartets | PhantomThreshold# | WA | 0ms | 4576kb | C++20 | 2.1kb | 2024-09-12 18:40:57 | 2024-09-12 18:40:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n;
cin>>n;
//[x,ty,y,s,k,yn]
vector<tuple<int,int,int,int,int,int>> ops(n+5);
for(int i=1;i<=n;i++)
{
int x,y,s;
string ty,k,res;
cin>>x>>ty;
if(ty=="A")
{
cin>>y>>s>>k>>res;
ops[i]={x,0,y,s,k[0]-'A'+1,(res=="yes")};
}
else
{
cin>>s;
ops[i]={x,1,0,s,0,0};
}
}
vector valid(11,vector(5,vector(5,vector(5,vector(5,0)))));
for(int suit=1;suit<=8;suit++)
{
auto solve=[&](vector<int> pip)
{
for(int i=1;i<=n;i++)
{
auto [x,ty,y,s,k,yn]=ops[i];
if(s!=suit)continue;
if(ty==1)
{
if(pip[1]!=x or pip[2]!=x or pip[3]!=x or pip[4]!=x)
return i;
}
else
{
if(pip[1]!=x and pip[2]!=x and pip[3]!=x and pip[4]!=x)
return i;
if(yn==0 and (pip[k]==y))
return i;
pip[k]=x;
}
}
return n+1;
};
vector<int> pip(5),cnt(5);
function<void(int)> dfs=[&](int dep)
{
if(dep==5)
{
valid[suit][cnt[1]][cnt[2]][cnt[3]][cnt[4]]=max(valid[suit][cnt[1]][cnt[2]][cnt[3]][cnt[4]],solve(pip));
return;
}
for(pip[dep]=1;pip[dep]<=4;pip[dep]++)
{
cnt[pip[dep]]++;
dfs(dep+1);
cnt[pip[dep]]--;
}
};
dfs(1);
}
auto chk=[&](int T)
{
vector dp(11,vector(9,vector(9,vector(9,vector(9,0)))));
dp[0][0][0][0][0]=1;
for(int suit=1;suit<=8;suit++)
{
for(int a=0;a<=8;a++)
for(int b=0;b<=8;b++)
for(int c=0;c<=8;c++)
for(int d=0;d<=8;d++)
{
if(dp[suit-1][a][b][c][d]==0)continue;
for(int da=0;da<=4 and a+da<=8;da++)
for(int db=0;da+db<=4 and b+db<=8;db++)
for(int dc=0;da+db+dc<=4 and c+dc<=8;dc++)
{
int dd=4-da-db-dc;
if(d+dd>8)continue;
if(valid[suit][da][db][dc][dd]>=T)
dp[suit][a+da][b+db][c+dc][d+dd]=1;
}
}
}
return dp[8][8][8][8][8];
};
int l=1,r=n+1;
while(l<r)
{
int mid=(l+r+1)/2;
if(chk(mid))l=mid;
else r=mid-1;
}
if(l==n+1)cout<<"yes\n";
else cout<<"no\n"<<l<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4576kb
input:
27 1 A 2 7A yes 1 Q 7 1 A 2 1A no 2 A 1 3A no 1 A 2 1B no 2 A 1 3A no 1 A 2 1C no 2 A 1 3A no 1 A 2 1D no 2 A 1 3A no 1 A 2 2A no 2 A 1 3A no 1 A 2 2B no 2 A 1 3A no 1 A 2 2C no 2 A 1 3A no 1 A 2 2D no 2 A 1 3A no 1 A 3 2A no 3 A 2 3A yes 3 Q 3 3 Q 4 3 A 4 1A no 4 A 2 5A yes 4 Q 5 4 Q 6 4 A 3 2A no
output:
no 23
result:
wrong answer 2nd lines differ - expected: '26', found: '23'