QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260331#7179. Fischer's Chess Guessing Gamesofija6TL 0ms7184kbC++232.7kb2023-11-22 01:35:432023-11-22 01:35:43

Judging History

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

  • [2023-11-22 01:35:43]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:7184kb
  • [2023-11-22 01:35:43]
  • 提交

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;
}

詳細信息

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

result: