QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#705165 | #9537. Chinese Chess | ucup-team134# | TL | 90ms | 4344kb | C++17 | 3.7kb | 2024-11-02 22:22:39 | 2024-11-02 22:22:39 |
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+1);
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);
/*{
for(auto p:opt){
printf("%i %i: %i\n",p.f,p.s,dist[p.f][tt.s][p.s]);
}
}*/
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: 0
Accepted
time: 17ms
memory: 4040kb
input:
4 2 1 2 3 2 5 2 7 12 9
output:
2 ? 7 0 ? 0 0 ! J
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 11ms
memory: 4036kb
input:
1 2 4 -1 1
output:
2 ? 0 0 ? 0 2 ! X
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 3ms
memory: 4032kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 7ms
memory: 4036kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 15ms
memory: 4324kb
input:
2 7 7 1 0 5 14
output:
2 ? 7 2 ? 0 0 ! J
result:
ok number is guessed.
Test #7:
score: 0
Accepted
time: 22ms
memory: 4296kb
input:
5 8 6 1 3 0 5 2 4 0 2 10 2
output:
2 ? 9 3 ? 0 0 ! J
result:
ok number is guessed.
Test #8:
score: 0
Accepted
time: 22ms
memory: 4332kb
input:
6 0 7 1 6 2 8 0 5 7 6 8 2 14 -1
output:
2 ? 8 1 ? 0 0 ! B
result:
ok number is guessed.
Test #9:
score: 0
Accepted
time: 27ms
memory: 4064kb
input:
7 6 5 3 0 3 2 4 1 4 0 2 4 5 2 11 4
output:
2 ? 7 8 ? 0 0 ! J
result:
ok number is guessed.
Test #10:
score: 0
Accepted
time: 28ms
memory: 4040kb
input:
8 3 3 2 5 6 2 7 4 1 4 3 0 2 4 3 4 6 4
output:
2 ? 7 4 ? 0 1 ! J
result:
ok number is guessed.
Test #11:
score: 0
Accepted
time: 27ms
memory: 4064kb
input:
9 2 7 2 4 2 5 2 2 2 1 2 0 2 6 2 3 2 8 11 9
output:
2 ? 8 2 ? 0 0 ! J
result:
ok number is guessed.
Test #12:
score: 0
Accepted
time: 32ms
memory: 4300kb
input:
10 4 0 0 0 5 0 7 0 8 0 1 0 6 0 9 0 2 0 3 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #13:
score: 0
Accepted
time: 29ms
memory: 4068kb
input:
9 1 8 1 2 1 5 1 6 1 3 1 4 1 0 1 1 1 7 11 8
output:
2 ? 7 2 ? 0 0 ! J
result:
ok number is guessed.
Test #14:
score: 0
Accepted
time: 87ms
memory: 4328kb
input:
10 0 4 5 4 8 4 2 4 4 4 7 4 3 4 9 4 6 4 1 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #15:
score: 0
Accepted
time: 90ms
memory: 4068kb
input:
9 4 6 4 5 4 7 4 4 4 1 4 3 4 0 4 8 4 2 11 12
output:
2 ? 8 1 ? 0 0 ! J
result:
ok number is guessed.
Test #16:
score: 0
Accepted
time: 30ms
memory: 4040kb
input:
10 9 2 5 2 1 2 8 2 6 2 7 2 2 2 0 2 4 2 3 2 9 -1
output:
2 ? 9 2 ? 0 0 ! B
result:
ok number is guessed.
Test #17:
score: 0
Accepted
time: 32ms
memory: 4044kb
input:
9 3 1 3 7 3 5 3 3 3 6 3 4 3 0 3 2 3 8 11 10
output:
2 ? 9 2 ? 0 0 ! J
result:
ok number is guessed.
Test #18:
score: 0
Accepted
time: 31ms
memory: 4344kb
input:
10 5 1 8 1 6 1 4 1 3 1 0 1 2 1 7 1 9 1 1 1 9 -1
output:
2 ? 9 1 ? 0 0 ! B
result:
ok number is guessed.
Test #19:
score: 0
Accepted
time: 30ms
memory: 4068kb
input:
9 1 6 1 4 1 3 1 7 1 8 1 5 1 2 1 1 1 0 11 8
output:
2 ? 7 2 ? 0 0 ! J
result:
ok number is guessed.
Test #20:
score: 0
Accepted
time: 32ms
memory: 4068kb
input:
10 5 0 9 0 1 0 2 0 3 0 6 0 7 0 4 0 0 0 8 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #21:
score: 0
Accepted
time: 30ms
memory: 4328kb
input:
9 0 3 0 5 0 7 0 0 0 4 0 8 0 1 0 6 0 2 11 7
output:
2 ? 6 2 ? 0 0 ! J
result:
ok number is guessed.
Test #22:
score: 0
Accepted
time: 32ms
memory: 4060kb
input:
10 1 0 9 0 4 0 2 0 8 0 7 0 5 0 3 0 0 0 6 0 9 -1
output:
2 ? 9 0 ? 0 1 ! B
result:
ok number is guessed.
Test #23:
score: 0
Accepted
time: 32ms
memory: 4036kb
input:
9 1 8 1 2 1 7 1 0 1 4 1 6 1 1 1 5 1 3 11 8
output:
2 ? 7 2 ? 0 0 ! J
result:
ok number is guessed.
Test #24:
score: 0
Accepted
time: 84ms
memory: 4048kb
input:
10 2 4 1 4 0 4 6 4 4 4 9 4 5 4 3 4 7 4 8 4 11 5
output:
2 ? 9 1 ? 0 0 ! J
result:
ok number is guessed.
Test #25:
score: 0
Accepted
time: 32ms
memory: 4124kb
input:
9 0 2 0 7 0 5 0 4 0 0 0 3 0 1 0 6 0 8 11 7
output:
2 ? 6 2 ? 0 0 ! J
result:
ok number is guessed.
Test #26:
score: 0
Accepted
time: 71ms
memory: 4068kb
input:
10 5 3 2 3 3 3 8 3 9 3 1 3 6 3 7 3 0 3 4 3 11 4
output:
2 ? 9 0 ? 0 0 ! J
result:
ok number is guessed.
Test #27:
score: -100
Time Limit Exceeded
input:
50 7 5 9 2 0 4 9 3 8 4 8 2 7 2 6 4 4 4 0 0 1 7 1 1 1 5 2 0 9 8 9 0 3 1 7 8 8 6 5 0 7 3 8 5 2 6 4 8 3 5 6 8 0 8 5 7 4 6 1 6 3 8 5 6 3 0 5 3 0 7 5 1 3 4 0 1 7 6 2 3 4 3 5 5 8 1 0 3 6 5 9 5 5 8 7 4 6 3 2 7 4 -1 3
output:
3 ? 9 3 ? 2 6 ? 7 5 ! X