QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#673418 | #4328. Dugput | Qingyu | 0 ✓ | 7ms | 10324kb | C++23 | 4.8kb | 2024-10-24 22:16:39 | 2024-10-24 22:28:15 |
Judging History
你现在查看的是测评时间为 2024-10-24 22:28:15 的历史记录
- [2024-10-24 22:16:39]
- 提交
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5005;
int tid,T;
bool ri[MAXN][MAXN],dw[MAXN][MAXN];
bool vis[MAXN][MAXN];
map<array<int,6>,string> mp;
int max_len(int n,int m,int x1,int y1,int x2,int y2){
if(x1==x2&&y1==y2) return 1;
if(n>m) return max_len(m,n,y1,x1,y2,x2);
if(x1>x2) return max_len(n,m,n+1-x1,y1,n+1-x2,y2);
if(y1>y2) return max_len(n,m,x1,m+1-y1,x2,m+1-y2);
if(n==1) return y2-y1+1;
if(n==2&&x2-x1==1&&y2-y1<=1) return max(y1+y2,2*m+2-y1-y2);
if(n*m&1) return n*m-((x1+y1)&1)-((x2+y2)&1);
if(n==3&&((x1+x2+y1+y2)&1)&&((y2-y1>=2&&((x1+y1)&1))||(x1==2&&x2==2&&(y1&1)))) return n*m-2;
return n*m-(~(x1+x2+y1+y2)&1);
}
string replace(string s,char L,char R,char U,char D){
for(int i=0;i<s.length();i++){
if(s[i]=='L') s[i]=L;
else if(s[i]=='R') s[i]=R;
else if(s[i]=='U') s[i]=U;
else if(s[i]=='D') s[i]=D;
}
return s;
}
string rev(string s){
reverse(s.begin(),s.end());
return replace(s,'R','L','D','U');
}
string solve(int n,int m,int x1,int y1,int x2,int y2){
if(x1==x2&&y1==y2) return (string){};
if(mp.count({n,m,x1,y1,x2,y2})) return mp[{n,m,x1,y1,x2,y2}];
if(n>m) return replace(solve(m,n,y1,x1,y2,x2),'U','D','L','R');
if(x1>x2) return replace(solve(n,m,n+1-x1,y1,n+1-x2,y2),'L','R','D','U');
if(y1>y2) return replace(solve(n,m,x1,m+1-y1,x2,m+1-y2),'R','L','U','D');
if(n==1) return string(y2-y1,'R');
int C=max_len(n,m,x1,y1,x2,y2);
for(int x=1;x<=n;x++) if(x1<=x&&x<x2) for(int y=1;y<=m;y++){
if(C==max_len(x,m,x1,y1,x,y)+max_len(n-x,m,1,y,x2-x,y2)){
return solve(x,m,x1,y1,x,y)+"D"+solve(n-x,m,1,y,x2-x,y2);
}
}
for(int y=1;y<=m;y++) if(y1<=y&&y<y2) for(int x=1;x<=n;x++){
if(C==max_len(n,y,x1,y1,x,y)+max_len(n,m-y,x,1,x2,y2-y)){
return solve(n,y,x1,y1,x,y)+"R"+solve(n,m-y,x,1,x2,y2-y);
}
}
if(n==3&&y1==y2){
int x3=6-x1-x2;
if(3+max_len(3,y1-1,x1,y1-1,x3,y1-1)+max_len(3,m-y1,x3,1,x2,1)==C){
return "L"+solve(3,y1-1,x1,y1-1,x3,y1-1)+"RR"+
solve(3,m-y1,x3,1,x2,1)+"L";
}
if(3+max_len(3,m-y1,x1,1,x3,1)+max_len(3,y1-1,x3,y1-1,x2,y1-1)==C){
return "R"+solve(3,m-y1,x1,1,x3,1)+"LL"+
solve(3,y1-1,x3,y1-1,x2,y1-1)+"R";
}
}else if(n==3&&y2-y1==1){
assert(x1==1&&x2==3);
if(6+max_len(3,m-y2,1,1,2,1)+max_len(3,y1-1,2,y1-1,3,y1-1)==C)
return "RR"+solve(3,m-y2,1,1,2,1)+"LLL"+
solve(3,y1-1,2,y1-1,3,y1-1)+"RR";
}
bool flag=(x1==x2);string s;
if(flag) swap(n,m),swap(x1,y1),swap(x2,y2);
for(int o:{0,1}){
for(int i=x2+1;i<=n;i++){
if(n+max_len(n,m-y1,1,1,i,1)+max_len(n,y1-1,n,y1-1,i-1,y1-1)==C){
s=string(x1-1,'U')+"R"+solve(n,m-y1,1,1,i,1)+"L"+string(n-i,'D')+"L"+
solve(n,y1-1,n,y1-1,i-1,y1-1)+"R"+string(i-1-x2,'U');
if(o) s=replace(s,'R','L','U','D');
if(!flag) return s;
return replace(s,'U','D','L','R');
}else if(n+max_len(n,m-y1,1,1,n,1)+max_len(n,y1-1,i,y1-1,i-1,y1-1)==C){
s=string(x1-1,'U')+"R"+solve(n,m-y1,1,1,n,1)+"L"+string(n-i,'U')+"L"+
solve(n,y1-1,i,y1-1,i-1,y1-1)+"R"+string(i-1-x2,'U');
if(o) s=replace(s,'R','L','U','D');
if(!flag) return s;
return replace(s,'U','D','L','R');
}
}
for(int i=1;i<x1;i++){
if(n+max_len(n,m-y1,i+1,1,i,1)+max_len(n,y1-1,1,y1-1,n,y1-1)==C){
s=string(x1-i-1,'U')+"R"+solve(n,m-y1,i+1,1,i,1)+"L"+string(i-1,'U')+"L"+
solve(n,y1-1,1,y1-1,n,y1-1)+"R"+string(n-x2,'U');
if(o) s=replace(s,'R','L','U','D');
if(!flag) return s;
return replace(s,'U','D','L','R');
}else if(n+max_len(n,m-y1,i+1,1,1,1)+max_len(n,y1-1,i,y1-1,n,y1-1)==C){
s=string(x1-i-1,'U')+"R"+solve(n,m-y1,i+1,1,1,1)+"L"+string(i-1,'D')+
"L"+solve(n,y1-1,i,y1-1,n,y1-1)+"R"+string(n-x2,'U');
if(o) s=replace(s,'R','L','U','D');
if(!flag) return s;
return replace(s,'U','D','L','R');
}
}
y1=y2=m+1-y1;
}
assert(0);
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
cin>>tid>>T;
if(tid<=4)tid=0;
else tid=1;
while(T--){
int n,m,x1,y1,x2,y2;
cin>>n>>m>>x1>>y1>>x2>>y2;
if(tid) cout<<max_len(n,m,x1,y1,x2,y2)<<'\n';
else{
string s=solve(n,m,x1,y1,x2,y2);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j]=ri[i][j]=dw[i][j]=0;
int x=x1,y=y1;
for(char c:s){
vis[x][y]=true;
if(c=='L'){
ri[x][--y]=true;
}else if(c=='R'){
ri[x][y++]=true;
}else if(c=='U'){
dw[--x][y]=true;
}else{
dw[x++][y]=true;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<"o*"[(i==x1&&j==y1)||(i==x2&&j==y2)];
if(j<m) for(int o:{0,1}) cout<<" -"[ri[i][j]];
}
cout<<'\n';
if(i<n){
for(int j=1;j<=m;j++){
cout<<" |"[dw[i][j]];
if(j<m) cout<<" ";
}
cout<<'\n';
}
}
}
}
cerr<<"Running time: "<<1.*clock()/CLOCKS_PER_SEC<<'\n';
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 7ms
memory: 10324kb
input:
1 1562 15 6 1 6 15 1 15 6 5 6 11 1 15 6 15 2 1 5 15 6 1 6 1 3 15 6 15 6 11 6 15 6 1 1 4 2 15 6 2 1 9 2 15 6 4 5 9 4 15 6 4 5 4 6 15 6 9 2 3 2 15 6 9 2 6 5 2 41 1 41 2 1 2 41 1 24 2 9 2 41 2 2 1 10 2 41 1 1 1 14 2 41 2 1 1 10 2 41 2 16 2 17 2 41 1 28 2 35 2 41 2 9 1 36 2 41 1 18 ...
output:
o--o--o o--o * | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | | | o--o o o o o | | | ...
result:
wrong answer (2, 5) and (3, 6) is not connected! (test case 1499)
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 3976kb
input:
5 1562 165 500 1 500 165 500 165 500 78 500 1 401 165 500 165 469 104 500 165 500 1 1 165 298 165 500 165 1 1 499 165 500 165 1 4 122 165 500 8 1 85 361 165 500 112 191 152 254 165 500 112 191 114 190 165 500 49 106 64 350 165 500 49 106 48 108 22 500 22 500 22 1 22 500 20 1 1 387 22 ...
output:
82499 82499 82499 82500 82499 82499 82500 82500 82500 82500 82500 11000 11000 10999 10999 10999 11000 10999 11000 11000 11000 10999 10499 10500 10500 10500 10500 10500 10500 10500 10500 10500 10499 30000 30000 29999 29999 29999 30000 30000 29999 30000 29999 30000 39999 39999 40000 40000 40000 40000 ...
result:
wrong answer invalid map: (1, 1) is , but it should be either o or * (test case 1349)