QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #708477 | #9537. Chinese Chess | Brno (Bocheng Jiang, Zhenyu Wang, Taixiang Wang) | WA | 8ms | 16188kb | C++14 | 5.6kb | 2024-11-03 22:48:16 | 2024-11-03 22:48:18 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
// #define endl '\n'
#define siz(a) int(a.size())
struct node{
int x,y,tp;
}p[400100];
vector<node>a,res;
int inf=0x3f3f3f3f;
struct dinic__b_y__i__c__e____c__u__p{
#define pn 2010
#define en 401000
int head[pn],to[en],nxt[en],v[en],cv[en],cnt=1;
int d[pn],vis[pn],s,t,cur[pn];
void ad(int u,int e,int val){
nxt[++cnt]=head[u];
to[cnt]=e;
v[cnt]=val;
head[u]=cnt;
}
int add(int u,int e,int val){
// cout<<u<<' '<<e<<' '<<val<<' '<<co<<endl;
ad(u,e,val);
ad(e,u,0);
return cnt-1;
}
queue<int>q;
bool bfs(){
while(!q.empty())q.pop();
memset(d,0,sizeof(d));
d[s]=1;q.push(s);cur[s]=head[s];
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]){
if(!d[to[i]]&&v[i]){
cur[to[i]]=head[to[i]];
d[to[i]]=d[u]+1;
if(to[i]==t)return 1;
q.push(to[i]);
}
}
}
return 0;
}
int dfs(int u,int flow){
if(u==t||flow<=0)return flow;
int re=0;
for(int &i=cur[u];i;i=nxt[i]){
if(d[to[i]]!=d[u]+1||!v[i])continue;
int tmp=dfs(to[i],min(flow,v[i]));
flow-=tmp,v[i]-=tmp;
re+=tmp,v[i^1]+=tmp;
if(!flow)break;
}
return re;
}
int dinic(){
int ans=0;
while(bfs()){
// cout<<ans<<endl;
ans+=dfs(s,inf);
}
return ans;
}
void clear(){
memset(head,0,sizeof(head));
cnt=1;
}
void cp(){
memcpy(cv,v,sizeof(v));
}
void remake(){
memcpy(v,cv,sizeof(cv));
}
}din;
int n,dis[20][20][10][20][20],tot,id[11][11][2],ed[11][11];
int x1[]={1,-1,0,0},y11[]={0,0,-1,1};
int x2[]={1,1,-1,-1},y2[]={1,-1,1,-1};
int x4[]={2,2,-2,-2,1,1,-1,-1},y4[]={1,-1,1,-1,2,-2,2,-2};
int x5[]={2,2,-2,-2},y5[]={2,-2,2,-2};
int x6[]={1,0,0},y6[]={0,1,-1};
char wcnm[]={' ','J','S','C','M','X','B'};
void solveclr(){
}
bool ck(int x,int y){
return x>=0&&y>=0&&x<=9&&y<=8;
}
void calc(){
queue<node>q;
memset(dis,0,sizeof(dis));
for(int r=0;r<=9;r++){
for(int c=0;c<=9;c++){
for(int tp=1;tp<=6;tp++){
dis[r][c][tp][r][c]=1;
q.push(node{r,c,tp});
while(!q.empty()){
node u=q.front();q.pop();
if(tp==1){
for(int i=0;i<4;i++){
node v=u;v.x+=x1[i],v.y+=y11[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==2){
for(int i=0;i<4;i++){
node v=u;v.x+=x2[i],v.y+=y2[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==3){
for(int i=-9;i<=9;i++){
node v=u;v.x+=i;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
for(int i=-9;i<=9;i++){
node v=u;v.y+=i;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==4){
for(int i=0;i<8;i++){
node v=u;v.x+=x4[i],v.y+=y4[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==5){
for(int i=0;i<4;i++){
node v=u;v.x+=x5[i],v.y+=y5[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
if(tp==6){
if(u.x>4)for(int i=0;i<3;i++){
node v=u;v.x+=x6[i],v.y+=y6[i];
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
else{
node v=u;v.x++;
if(ck(v.x,v.y)&&dis[r][c][tp][v.x][v.y]==0){
dis[r][c][tp][v.x][v.y]=dis[r][c][tp][u.x][u.y]+1;
q.push(v);
}
}
}
}
}
}
}
}
void solve(){
solveclr();
calc();
cin>>n;
for(int i=1;i<=n;i++){
int x,y;cin>>x>>y;
for(int i=1;i<=6;i++)a.push_back(node{x,y,i});
}
din.s=++tot,din.t=++tot;
for(int i=0;i<=9;i++){
for(int j=0;j<=8;j++){
id[i][j][0]=++tot;
id[i][j][1]=++tot;
ed[i][j]=din.add(id[i][j][0],id[i][j][1],1);
}
}
for(auto x:a){
for(auto y:a){
if(x.tp!=y.tp){
vector<int>tmp;
for(int i=0;i<=9;i++){
for(int j=0;j<=8;j++){
if(dis[x.x][x.y][x.tp][i][j]!=dis[y.x][y.y][y.tp][i][j]){
tmp.push_back(id[i][j][0]);
}
}
}
din.add(din.s,tmp[0],inf);
for(int i=1;i<tmp.size();i++){
din.add(tmp[i-1]+1,tmp[i],inf);
}
din.add(tmp[tmp.size()-1]+1,din.t,inf);
}
}
}
din.dinic();
int cnt=0;
for(int i=0;i<=9;i++){
for(int j=0;j<=8;j++){
// cout<<din.d[id[i][j][0]]<<' '<<din.d[id[i][j][1]]
if(din.d[id[i][j][0]]!=0&&din.d[id[i][j][1]]==0){
cnt++;
}
}
}
cout<<cnt<<endl;
for(int i=0;i<=9;i++){
for(int j=0;j<=8;j++){
if(din.d[id[i][j][0]]!=0&&din.d[id[i][j][1]]==0){
cout<<"? "<<i<<' '<<j<<endl;
int in;cin>>in;
res.push_back(node{i,j,in+1});
}
}
}
for(auto x:a){
int fl=1;
for(auto y:res){
if(dis[x.x][x.y][x.tp][y.x][y.y]!=y.tp){
fl=0;break;
}
}
if(fl){
cout<<"! "<<wcnm[x.tp]<<endl;
return;
}
}
}
int main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT;
// cin>>TTT;
TTT=1;
while(TTT--)solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 15144kb
input:
1 9 0 8
output:
1 ? 1 8 ! S
result:
ok number is guessed.
Test #2:
score: 0
Accepted
time: 2ms
memory: 15556kb
input:
4 2 1 2 3 2 5 2 7 5 2
output:
2 ? 4 8 ? 5 0 ! M
result:
ok number is guessed.
Test #3:
score: 0
Accepted
time: 0ms
memory: 16188kb
input:
1 2 4 -1 2
output:
2 ? 0 1 ? 0 2 ! S
result:
ok number is guessed.
Test #4:
score: 0
Accepted
time: 3ms
memory: 15100kb
input:
1 5 0 6
output:
1 ? 3 6 ! S
result:
ok number is guessed.
Test #5:
score: 0
Accepted
time: 5ms
memory: 15040kb
input:
1 6 0 6
output:
1 ? 0 2 ! S
result:
ok number is guessed.
Test #6:
score: 0
Accepted
time: 0ms
memory: 15496kb
input:
2 7 7 1 0 4 -1
output:
2 ? 1 4 ? 1 5 ! S
result:
ok number is guessed.
Test #7:
score: -100
Wrong Answer
time: 8ms
memory: 16076kb
input:
5 8 6 1 3 0 5 2 4 0 2
output:
4 ? 3 5
result:
wrong answer solution think m=4, while jury think m=2.