QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#224811#7179. Fischer's Chess Guessing Gamesofija6TL 75ms47792kbC++172.5kb2023-10-23 15:16:452023-10-23 15:16:46

Judging History

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

  • [2023-10-23 15:16:46]
  • 评测
  • 测评结果:TL
  • 用时:75ms
  • 内存:47792kb
  • [2023-10-23 15:16:45]
  • 提交

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

result: