QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#224811 | #7179. Fischer's Chess Guessing Game | sofija6 | TL | 75ms | 47792kb | C++17 | 2.5kb | 2023-10-23 15:16:45 | 2023-10-23 15:16:46 |
Judging History
answer
#include <bits/stdc++.h>
#define ll int
using namespace std;
vector<string> v;
vector<pair<string,ll> > S;
void Create(string s,ll b,ll p,ll k,ll n,ll q,ll r)
{
if ((ll)s.size()==8)
{
v.push_back(s);
return;
}
string c=s;
if (!b || (b==1 && p!=s.size()%2))
{
c+='B';
Create(c,b+1,s.size()%2,k,n,q,r);
c=s;
}
if (!k && r==1)
{
c+='K';
Create(c,b,p,k+1,n,q,r);
c=s;
}
if (n!=2)
{
c+='N';
Create(c,b,p,k,n+1,q,r);
c=s;
}
if (!q)
{
c+='Q';
Create(c,b,p,k,n,q+1,r);
c=s;
}
if (!r || (r==1 && k==1))
{
c+='R';
Create(c,b,p,k,n,q,r+1);
}
return;
}
map<string,vector<string> > c[10];
vector<string> w;
bool Check(string x)
{
for (auto i : S)
{
ll diff=0;
for (ll j=0;j<8;j++)
diff+=(i.first[j]!=x[j]);
if (diff!=i.second || !diff)
return false;
}
return true;
}
string Get_Min()
{
ll maxx=INT_MAX;
string ans;
map<string,ll> cnt[10];
for (auto i : v)
{
for (ll j=0;j<9;j++)
cnt[j][i]=c[j][i].size();
}
for (auto i : S)
{
for (auto j : v)
{
ll d=0;
for (ll p=0;p<8;p++)
d+=(i.first[p]!=j[p]);
cnt[d][j]--;
cnt[d][i.first]--;
}
}
for (auto i : w)
{
ll cur=0;
for (ll j=0;j<9;j++)
cur=max(cur,cnt[j][i]);
if (cur<maxx && Check(i))
{
maxx=cur;
ans=i;
}
}
return ans;
}
int main()
{
string s="";
Create(s,0,0,0,0,0,0);
for (auto i : v)
{
for (auto j : v)
{
ll cnt=0;
for (ll p=0;p<8;p++)
cnt+=(i[p]!=j[p]);
c[cnt][i].push_back(j);
}
}
string x="";
ll n,a;
while (true)
{
if (x=="")
cin >> x;
cin >> n;
S.clear();
w=v;
s=Get_Min();
while (true)
{
cout << s << "\n";
cin >> a;
a=8-a;
if (!a)
{
cin >> x;
if (x=="END")
return 0;
break;
}
w=c[a][s];
S.push_back({s,a});
s=Get_Min();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 75ms
memory: 47792kb
input:
GAME 1 1 3 4 3 6 8 END
output:
NRBBNKQR RKBNQBRN RQKBBNRN RBNQBKRN RKQBBRNN RKRBBQNN
result:
ok (c) correct after 1 tests, max moves 6 (1 test case)
Test #2:
score: -100
Time Limit Exceeded
input:
GAME 1 1 3 4 3 6 8 GAME 2 2 2 4 4 8 GAME 3 1 2 2 5 8 GAME 4 1 4 5 2 8 GAME 5 2 2 4 2 3 6
output:
NRBBNKQR RKBNQBRN RQKBBNRN RBNQBKRN RKQBBRNN RKRBBQNN NRBBNKQR RBBNQKRN RKNBQNBR RKNNBBQR RKRBBNQN NRBBNKQR RKBNQBRN RBNNBQKR RNKBBNRQ RKRBBNNQ NRBBNKQR RKBNQBRN RKQBBNRN RBQNBKRN RKRBQNBN NRBBNKQR RBBNQKRN RKNBQNBR RKNNBBQR RBKQNNBR RKQBNRBN