QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260331 | #7179. Fischer's Chess Guessing Game | sofija6 | TL | 0ms | 7184kb | C++23 | 2.7kb | 2023-11-22 01:35:43 | 2023-11-22 01:35:43 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
#define MAXN 970
using namespace std;
vector<string> v;
bitset<MAXN> ch;
ll same[MAXN][MAXN],ans;
ll Num_Of_Same(ll i,ll j)
{
ll cnt=0;
for (ll l=0;l<8;l++)
cnt+=v[i][l]==v[j][l];
return cnt;
}
bool Cmp(ll i,ll j)
{
return i>j;
}
void Solve(ll a)
{
for (ll i=0;i<v.size();i++)
{
if (same[ans][i]!=a)
ch[i]=false;
}
ll maxx[10];
for (ll i=0;i<9;i++)
maxx[i]=1e6;
for (ll i=0;i<v.size();i++)
{
if (!ch[i])
continue;
ll cnt[10]={0},m=-1;
for (ll j=0;j<v.size();j++)
{
if (!ch[j])
continue;
cnt[same[i][j]]++;
}
sort(cnt,cnt+9,Cmp);
bool yes=true;
for (ll j=0;j<9;j++)
{
if (cnt[j]==maxx[j])
continue;
if (cnt[j]>maxx[j])
{
yes=false;
break;
}
}
if (yes)
{
ans=i;
for (ll j=0;j<9;j++)
maxx[j]=cnt[j];
}
}
}
ll b,p,k,n,q,r,prevv;
string s;
void Create()
{
if ((ll)s.size()==8)
{
v.push_back(s);
return;
}
if (!b || (b==1 && p!=s.size()%2))
{
b++;
prevv=p;
p=s.size()%2;
s+='B';
Create();
p=prevv;
b--;
s.pop_back();
}
if (!k && r==1)
{
s+='K';
k++;
Create();
k--;
s.pop_back();
}
if (n!=2)
{
s+='N';
n++;
Create();
n--;
s.pop_back();
}
if (!q)
{
s+='Q';
q++;
Create();
q--;
s.pop_back();
}
if (!r || (r==1 && k==1))
{
s+='R';
r++;
Create();
r--;
s.pop_back();
}
return;
}
int main()
{
string x="";
ll ans0,a;
Create();
for (ll i=0;i<v.size();i++)
{
if (v[i]=="NRBBNKQR")
ans0=i;
}
for (ll i=0;i<v.size();i++)
{
for (ll j=0;j<v.size();j++)
{
ll cnt=Num_Of_Same(i,j);
same[i][j]=cnt;
}
}
while (true)
{
cin >> x;
if (x=="END")
return 0;
cin >> n;
ans=ans0;
for (ll i=0;i<v.size();i++)
ch[i]=1;
while (true)
{
cout << v[ans] << "\n";
cin >> a;
if (a==8)
break;
Solve(a);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7184kb
input:
GAME 1 1 0 3 2 8 END
output:
NRBBNKQR BBNNQRKR NNRKBQRB NQRKRBBN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 5 (1 test case)
Test #2:
score: -100
Time Limit Exceeded
input:
GAME 1 1 0 3 2 8 GAME 2 2 0 0 8 GAME 3 1 0 2 0 4 8 GAME 4 1 1 3 2 4 8 GAME 5 2 1 2 0 2 2
output:
NRBBNKQR BBNNQRKR NNRKBQRB NQRKRBBN RKRBBQNN NRBBNKQR BBNQNRKR NNBRKBRQ RKRBBNQN NRBBNKQR BBNNQRKR NNRKBQRB QNBRKBRN RKRQNNBB RKRBBNNQ NRBBNKQR BBNNQRKR BNRBKNRQ BNRKRBQN RNQBKRBN RKRBQNBN NRBBNKQR BBNQNRKR BNQBRKRN BRKNRNQB NBBRKQRN RNBBKRNQ RKRBNQBN