QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#260326#7179. Fischer's Chess Guessing Gamesofija6TL 5ms7108kbC++232.6kb2023-11-22 01:30:492023-11-22 01:30:50

Judging History

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

  • [2023-11-22 01:30:50]
  • 评测
  • 测评结果:TL
  • 用时:5ms
  • 内存:7108kb
  • [2023-11-22 01:30:49]
  • 提交

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);
        for (ll j=0;j<9;j++)
        {
            if (cnt[j]>maxx[j])
                break;
            if (cnt[j]<maxx[j])
            {
                for (ll l=0;l<9;l++)
                    maxx[l]=cnt[l];
                ans=i;
                break;
            }
        }
    }
}
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: 5ms
memory: 7108kb

input:

GAME 1
1
2
2
8
END

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRBBQNN

result:

ok (c) correct after 1 tests, max moves 4 (1 test case)

Test #2:

score: -100
Time Limit Exceeded

input:

GAME 1
1
2
2
8
GAME 2
2
1
0
1
2
8
GAME 3
1
2
2
6
8
GAME 4
1
2
1
0
3
3

output:

NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRBBQNN
NRBBNKQR
RBBNKQNR
QRKNNRBB
NBNRBKRQ
BQNBRNKR
RKRBBNQN
NRBBNKQR
BNRKQBNR
RNBQKRNB
RKRBBQNN
RKRBBNNQ
NRBBNKQR
BNRKQBNR
RNBQKRNB
BRNNKBRQ
NQRKRNBB
QBRKNRBN
RKRBQNBN

result: