QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#254161#7179. Fischer's Chess Guessing Gamesofija6TL 3ms7132kbC++172.7kb2023-11-18 02:49:312023-11-18 02:49:31

Judging History

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

  • [2023-11-18 02:49:31]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:7132kb
  • [2023-11-18 02:49:31]
  • 提交

answer

#include <bits/stdc++.h>
#define ll int
#define MAXN 970
using namespace std;
vector<string> v;
vector<ll> startt[10],d[10],cur;
ll diff[MAXN][MAXN];
ll ans;
void Solve(ll a)
{
    ll prev=ans;
    cur=d[a];
    ll maxx=INT_MAX;
    for (ll i : cur)
    {
        if (i==ans)
            continue;
        ll cnt[10]={0},m=0;
        for (ll j : cur)
        {
            if (j==ans)
                continue;
            cnt[diff[i][j]]++;
            m=max(m,cnt[diff[i][j]]);
        }
        if (m<maxx && i!=ans)
        {
            maxx=m;
            ans=i;
        }
    }
    for (ll i=0;i<9;i++)
        d[i].clear();
    for (ll i : cur)
    {
        if (i==prev)
            continue;
        d[diff[ans][i]].push_back(i);
    }
}
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;
    Create();
    ll a;
    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=i+1;j<v.size();j++)
        {
            ll cnt=0;
            for (ll p=0;p<8;p++)
                cnt+=(v[i][p]!=v[j][p]);
            diff[i][j]=cnt;
            diff[j][i]=cnt;
        }
    }
    for (ll i=0;i<v.size();i++)
    {
        ll cnt=0;
        for (ll j=0;j<8;j++)
            cnt+=(v[ans0][j]!=v[i][j]);
        startt[cnt].push_back(i);
    }
    while (true)
    {
        if (x=="")
            cin >> x;
        cin >> n;
        ans=ans0;
        while (true)
        {
            cout << v[ans] << "\n";
            cin >> a;
            a=8-a;
            if (ans==ans0)
                d[a]=startt[a];
            if (!a)
            {
                cin >> x;
                if (x=="END")
                    return 0;
                break;
            }
            Solve(a);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7132kb

input:

GAME 1
1
2
2
4
3
8
END

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRQNBBN
RKBNQBRN
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
2
2
4
3
8
GAME 2
2
1
0
2
8
GAME 3
1
2
2
3
0
8
GAME 4
1
2
1
0
3
3

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRQNBBN
RKBNQBRN
RKRBBQNN
NRBBNKQR
RBBNKQNR
BRNNQKRB
NNRQBBKR
RKRBBNQN
NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRQNBBN
BRNQKBRN
RKRBBNNQ
NRBBNKQR
BNRKQBNR
RNBQKRNB
BRNNKBRQ
QBRKNRBN
NQRKRNBB
RKRBQNBN

result: