QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#224643 | #7179. Fischer's Chess Guessing Game | dozicc | TL | 5ms | 7628kb | C++14 | 3.8kb | 2023-10-23 06:56:18 | 2023-10-23 06:56:18 |
Judging History
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+1; 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: 5ms
memory: 7628kb
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 0 0 0 2
output:
NRNBBKQR RQKBBNRN RQBBNNKR RKNQBNRB RKQBBRNN RKRBBQNN NRNBBKQR NRBQNBKR NRBQNBKR NRBQNBKR NRBQNBKR RBNNBKRQ NRNBBKQR