QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#705149 | #9537. Chinese Chess | ucup-team134# | RE | 7ms | 4032kb | C++17 | 3.6kb | 2024-11-02 22:19:00 | 2024-11-02 22:19:05 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128
using namespace std;
mt19937 rng(time(NULL));
const int N=90;
int dist[N][N][6];
string tp="JSCMXB";
vector<pair<int,int>> gt2(int x,int y,int k){
if(k==0){
return {{x+1,y},{x-1,y},{x,y+1},{x,y-1}};
}
if(k==1){
return {{x+1,y+1},{x+1,y-1},{x-1,y+1},{x-1,y-1}};
}
if(k==2){
vector<pair<int,int>> a;
for(int X=0;X<10;X++){
if(X!=x)a.pb({X,y});
}
for(int Y=0;Y<9;Y++){
if(Y!=y)a.pb({x,Y});
}
return a;
}
if(k==3){
return {{x+2,y+1},{x+2,y-1},{x-2,y+1},{x-2,y-1},{x+1,y+2},{x+1,y-2},{x-1,y+2},{x-1,y-2}};
}
if(k==4){
return {{x+2,y+2},{x+2,y-2},{x-2,y+2},{x-2,y-2}};
}
if(k==5){
if(x<4)return {{x+1,y}};
return {{x+1,y},{x,y-1},{x,y+1}};
}
assert(0);
return {};
}
vector<pair<int,int>> gt(int x,int y,int k){
auto a=gt2(x,y,k);
vector<pair<int,int>> ans;
for(auto p:a){
if(p.f>=0&&p.f<10&&p.s>=0&&p.s<9)ans.pb(p);
}
return ans;
}
vector<pair<int,int>> pr(vector<pair<int,int>> &tr,int sq,int ds){
vector<pair<int,int>> ans;
for(auto p:tr){
if(dist[p.f][sq][p.s]==ds){
ans.pb(p);
}
}
return ans;
}
pair<int,int> calc(vector<pair<int,int>> opt,int bound){
bool sameType=1;
for(int i=1;i<sz(opt);i++){
if(opt[i].s!=opt[i-1].s)sameType=0;
}
if(sameType){
return {0,opt[0].s};
}
if(bound==0)return {1,-1};
//printf("Doing %i %i\n",sz(opt),bound);
vector<pair<int,int>> ord;
vector<vector<pair<int,int>>> opts(N+1);
for(int sq=0;sq<N;sq++){
int mxs=0;
for(int i=0;i<=N;i++)opts[i].clear();
for(auto p:opt){
int dd=dist[p.f][sq][p.s];
opts[dd+1].pb(p);
}
for(int i=0;i<=N;i++){
if(sz(opts[i])){
mxs=max(mxs,sz(opts[i]));
}
}
ord.pb({mxs,sq});
}
int ans=bound;
sort(all(ord));
int gde=-1;
for(auto d:ord){
//printf("trying: %i %i\n",d.f,d.s);
int sq=d.s;
for(int i=0;i<=N;i++)opts[i].clear();
for(auto p:opt){
int dd=dist[p.f][sq][p.s];
opts[dd+1].pb(p);
}
int myans=0;
for(int i=0;i<=N;i++){
if(sz(opts[i])){
myans=max(myans,calc(opts[i],ans-1).f);
if(myans>=ans)break;
}
}
myans++;
//printf("Found %i!\n",myans);
if(myans<ans){
ans=myans;
gde=sq;
}
}
return {ans,gde};
}
int main()
{
for(int i=0;i<N;i++){
int x=i/9,y=i%9;
for(int k=0;k<6;k++){
for(int j=0;j<N;j++){
dist[i][j][k]=-1;
}
queue<pair<int,int>> q;
q.push({x,y});
dist[i][i][k]=0;
while(sz(q)){
int xx=q.front().f,yy=q.front().s;
q.pop();
for(auto p:gt(xx,yy,k)){
int o=p.f*9+p.s;
if(dist[i][o][k]==-1){
dist[i][o][k]=dist[i][xx*9+yy][k]+1;
q.push(p);
}
}
}
/*if(i==81){
printf("%i: %i\n",k,dist[i][3*9+6][k]);
}*/
}
}
int n;
scanf("%i",&n);
vector<pair<int,int>> opt;
for(int i=0;i<n;i++){
int x,y;
scanf("%i %i",&x,&y);
for(int k=0;k<6;k++){
opt.pb({x*9+y,k});
}
}
bool first=1;
int bound=INT_MAX/2;
while(1){
pair<int,int> tt=calc(opt,bound);
if(first){
printf("%i\n",tt.f);
fflush(stdout);
first=0;
}
if(tt.f==0){
printf("! %c\n",tp[tt.s]);
fflush(stdout);
break;
}
printf("? %i %i\n",tt.s/9,tt.s%9);
fflush(stdout);
int ds;
cin >> ds;
opt=pr(opt,tt.s,ds);
bound=tt.f-1;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 4032kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: -100
Runtime Error
input:
4 2 1 2 3 2 5 2 7 12
output:
2 ? 7 0 ? 0 -1