QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225689#7179. Fischer's Chess Guessing Gamesofija6ML 13ms3808kbC++172.4kb2023-10-24 23:09:342023-10-24 23:09:35

Judging History

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

  • [2023-10-24 23:09:35]
  • 评测
  • 测评结果:ML
  • 用时:13ms
  • 内存:3808kb
  • [2023-10-24 23:09:34]
  • 提交

answer

#include <bits/stdc++.h>
#define ll int
using namespace std;
vector<string> v;
vector<pair<string,ll> > S;
set<string> cor;
string Get_Min()
{
    ll maxx=INT_MAX;
    string ans;
    set<string> ss;
    for (auto j : cor)
    {
        for (auto i : S)
        {
            ll d=0;
            for (ll p=0;p<8;p++)
                d+=(i.first[p]!=j[p]);
            if (d!=i.second)
            {
                ss.insert(j);
                break;
            }
        }
    }
    for (auto i : ss)
        cor.erase(i);
    ll cnt[10]={0},cur=0,diff;
    for (auto i : cor)
    {
        for (ll j=0;j<9;j++)
            cnt[j]=0;
        cur++;
        for (auto l : cor)
        {
            if (i==l)
                continue;
            diff=0;
            for (ll p=0;p<8;p++)
                diff+=(i[p]!=l[p]);
            cnt[diff]++;
            cur=max(cur,cnt[diff]);
        }
        if (cur<maxx)
        {
            ans=i;
            maxx=cur;
        }
    }
    return ans;
}
ll b,p,k,n,q,r;
void Create(string s)
{
    if ((ll)s.size()==8)
    {
        v.push_back(s);
        return;
    }
    string c=s;
    if (!b || (b==1 && p!=s.size()%2))
    {
        c+='B';
        b++;
        ll prev=p;
        p=s.size()%2;
        Create(c);
        p=prev;
        b--;
        c=s;
    }
    if (!k && r==1)
    {
        c+='K';
        k++;
        Create(c);
        k--;
        c=s;
    }
    if (n!=2)
    {
        c+='N';
        n++;
        Create(c);
        n--;
        c=s;
    }
    if (!q)
    {
        c+='Q';
        q++;
        Create(c);
        q--;
        c=s;
    }
    if (!r || (r==1 && k==1))
    {
        c+='R';
        r++;
        Create(c);
        r--;
    }
    return;
}
int main()
{
    string s="",x="";
    Create(s);
    ll a;
    while (true)
    {
        if (x=="")
            cin >> x;
        cin >> n;
        S.clear();
        for (auto i : v)
            cor.insert(i);
        s=Get_Min();
        while (true)
        {
            cout << s << "\n";
            cin >> a;
            a=8-a;
            if (!a)
            {
                cin >> x;
                if (x=="END")
                    return 0;
                break;
            }
            S.push_back({s,a});
            s=Get_Min();
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 13ms
memory: 3808kb

input:

GAME 1
0
1
2
2
8
END

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN

result:

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

Test #2:

score: -100
Memory Limit Exceeded

input:

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

output:

BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNNQB
RKRBBQNN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKRBBNQN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKRNBBQ
QNRKRNBB
RKRBBNNQ
BBNNQRKR
BNQBRKRN
BQRKNNRB
BRKRNBQN
NBRKRQBN
RKRBQNBN
BBNNQRKR
NNBBRKRQ
NRKRBBQN
RKBRNQNB
RKRBNQBN
BBNNQRKR
NNBBRKRQ
NQRKBBRN
NRKQRNBB
RKRBNNBQ
BBNNQRKR
NNBBRKRQ
QRK...

result: