QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673418#4328. DugputQingyu0 ✓7ms10324kbC++234.8kb2024-10-24 22:16:392024-10-24 22:28:15

Judging History

你现在查看的是测评时间为 2024-10-24 22:28:15 的历史记录

  • [2024-10-24 22:48:27]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:1213ms
  • 内存:18612kb
  • [2024-10-24 22:43:45]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:10ms
  • 内存:8468kb
  • [2024-10-24 22:28:15]
  • 管理员手动重测本题所有提交记录
  • 测评结果:0
  • 用时:7ms
  • 内存:10324kb
  • [2024-10-24 22:21:26]
  • 管理员手动重测本题所有提交记录
  • 测评结果:59.244865
  • 用时:1180ms
  • 内存:20748kb
  • [2024-10-24 22:16:40]
  • 评测
  • 测评结果:60
  • 用时:1208ms
  • 内存:16372kb
  • [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)