QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#224652#7179. Fischer's Chess Guessing GamedoziccTL 2ms7424kbC++143.8kb2023-10-23 07:10:132023-10-23 07:10:14

Judging History

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

  • [2023-10-23 07:10:14]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:7424kb
  • [2023-10-23 07:10:13]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<string>permutation;
map<char, int>check;
ll cnt[960][9], c=0;
int matrica[960][960], idmax[960];
void gen(int k, string s)
{
    if(k==8)
    {
        int pl1=0, pl2=0, pp1=0, pp2=0;
        for(int i=0; i<8; i++)
        {
            if(s[i]=='B'){if(pl1!=0)pl2=i+1; else pl1=i+1;}
            if(s[i]=='K'){if(pp1!=0 and pp2!=0)return; if(pp1==0 and pp2==0)return;}
            if(s[i]=='R'){if(pp1!=0)pp2=i+1; else pp1=i+1;}
        }
        if(pl1%2==pl2%2)return;
        permutation.push_back(s);
        return;
    }
    if(check['R']<2)
    {
        check['R']++; s+='R';
        gen(k+1, s); check['R']--; s.pop_back();
    }
    if(check['B']<2)
    {
        check['B']++; s+='B';
        gen(k+1, s); check['B']--; s.pop_back();
    }
    if(check['N']<2)
    {
        check['N']++; s+='N';
        gen(k+1, s); check['N']--; s.pop_back();
    }
    if(check['K']<1)
    {
        check['K']++; s+='K';
        gen(k+1, s); check['K']--; s.pop_back();
    }
    if(check['Q']<1)
    {
        check['Q']++; s+='Q';
        gen(k+1, s); check['Q']--; s.pop_back();
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    gen(0, "");
    string st;
    for(int i=0; i<960; i++)
    {
        for(int j=i; j<960; j++)
        {
            int br=0;
            for(int l=0; l<8; l++)
            {
                if(permutation[i][l]==permutation[j][l])br++;
            }
            cnt[i][br]++; cnt[j][br]++;
            matrica[i][j]=br; matrica[j][i]=br;
        }
    }
    int idx=-1, mini=INT_MAX;
    for(int i=0; i<960; i++)
    {
        ll lmax=0;
        for(int j=0; j<9; j++)lmax=max(lmax, cnt[i][j]);
        idmax[i]=lmax;
        if(lmax<=mini){mini=lmax; idx=i;}
    }
    getline(cin, st);
    int ans;
    while(true)
    {
        cout<<permutation[idx]<<endl;
        cin>>ans;
        if(ans==8)
        {
            string str; cin>>str;
            if(str=="END")return 0;
            else {int b; cin>>b; continue;}
        }
        int id=idx, t=2;
        vector<int>arr1, arr2;
        for(int i=0; i<960; i++)arr1.push_back(i);
        while(t--)
        {
            int pomid=-1, pommin=INT_MAX;
            for(int i=0; i<arr1.size(); i++)
            {
                if(matrica[arr1[i]][id]==ans)
                {
                    arr2.push_back(arr1[i]);
                    if(pommin>=idmax[arr1[i]]){pommin=idmax[arr1[i]]; pomid=arr1[i];}
                }
            }
            id=pomid;
            cout<<permutation[id]<<endl;
            cin>>ans;
            if(ans==8)
            {
                string str; cin>>str;
                if(str=="END")return 0;
                else {int b; cin>>b; continue;}
            }
            arr1.clear();
            pomid=-1; pommin=INT_MAX;
            for(int i=0; i<arr2.size(); i++)
            {
                if(matrica[arr2[i]][id]==ans)
                {
                    arr1.push_back(arr2[i]);
                    if(pommin>=idmax[arr2[i]]){pommin=idmax[arr2[i]]; pomid=arr2[i];}
                }
            }
            id=pomid;
            cout<<permutation[id]<<endl;
            cin>>ans;
            if(ans==8)
            {
                string str; cin>>str;
                if(str=="END")return 0;
                else {int b; cin>>b; continue;}
            }
            arr2.clear();
        }
        cout<<permutation[arr1[0]]<<endl;
        cin>>ans;
        if(ans==8)
        {
            string str; cin>>str;
            if(str=="END")return 0;
            else {int b; cin>>b; continue;}
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 7424kb

input:

GAME 1
2
4
2
3
6
8
END

output:

NRNBBKQR
RQKBBNRN
RQBBNNKR
RKNQBNRB
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
2
4
2
3
6
8
GAME 2
3
0
4
2
8
GAME 3
6
2
4
3
2
3

output:

NRNBBKQR
RQKBBNRN
RQBBNNKR
RKNQBNRB
RKQBBRNN
RKRBBQNN
NRNBBKQR
NRBQNBKR
RNQBBKRN
RBNNBKRQ
RKRBBNQN
RKRBBNQN
NRNBBKQR
RQKBBNRN
RQBBNNKR
RNBBQKRN
BRKBNNRQ
RKRBBNNQ

result: