QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110114#6515. Path PlanningzzzyzzzWA 26ms3644kbC++171.4kb2023-05-31 16:32:302023-05-31 16:32:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-31 16:32:33]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:3644kb
  • [2023-05-31 16:32:30]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
const int N=1e6+7;
typedef long long ll;
typedef pair<int,int> PII;

inline ll read() {
	ll c=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		c=c*10+ch-'0';
		ch=getchar();
	}
	return c*f;
}


int n,m,k;
vector<vector<int> > w;
PII vis[N];

bool check(int &res,set<pair<pair<int,int>,pair<int,int> > > &st) {
	int x=vis[res].fi,y=vis[res].se;
	pair<pair<int,int>,pair<int,int> > temp={{x,y},{-1,-1}};
	auto it=st.upper_bound(temp);
	if(it==st.end()) return false;
	
	int x1=it->se.fi,y1=it->se.se;
	int x2=it->fi.fi,y2=it->fi.se;
	if(x>=x1&&x<=x2&&y>=y1&&y<=y2) {
		st.erase(it);
		st.insert({{x,y},{x1,y1}});
		st.insert({{x2,y2},{x,y}});
		res++;
		return true;
	}else return false;
}

void solve() {
	w.clear();
	n=read(),m=read();	
	
	vector<int> p;
	w.push_back(p);
	for(int i=1;i<=n;i++) {
		vector<int> s;
		s.push_back(0);
		for(int j=1;j<=m;j++) {
			int c=read();
			s.push_back(c);
		}
		w.push_back(s);
	}
	
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			vis[w[i][j]]={i,j};
		}
	}
	
	int res=0;
	set<pair<pair<int,int>,pair<int,int> > > st;
	st.insert({{n,m},{1,1}});
	while(check(res,st)) ;
	printf("%d\n",res);
}

int main() {
	int T;
	T=read();
	while(T--) {
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3644kb

input:

2
2 3
1 2 4
3 0 5
1 5
1 3 0 4 2

output:

3
5

result:

ok 2 number(s): "3 5"

Test #2:

score: -100
Wrong Answer
time: 26ms
memory: 3564kb

input:

10000
2 9
4 0 3 5 2 7 16 11 12
9 13 14 17 10 8 15 1 6
4 8
19 23 22 13 29 4 17 26
30 6 25 3 15 24 18 14
12 8 7 9 27 5 0 10
11 16 31 20 2 28 1 21
1 6
3 2 0 1 4 5
2 3
4 2 0
3 5 1
5 1
4
0
3
2
1
1 3
1 0 2
8 10
9 50 8 0 41 57 60 30 23 65
64 21 36 12 10 5 58 19 38 67
71 52 45 17 77 4 59 51 22 25
56 49 79 2...

output:

9
2
6
3
5
3
14
13
5
9
5
7
6
9
7
4
6
7
13
9
10
9
6
1
5
7
4
2
10
4
18
5
12
3
7
6
9
2
1
5
6
10
8
4
2
5
2
5
7
13
6
10
3
10
3
6
9
8
3
10
2
3
3
5
8
4
7
7
7
8
8
6
6
5
3
7
8
13
3
3
6
5
4
3
10
5
12
7
2
11
6
7
5
10
9
5
3
10
2
5
3
8
7
10
5
4
10
4
6
5
9
4
10
6
3
5
4
4
7
4
8
3
12
5
4
5
8
6
8
3
7
9
3
6
12
4
6
6
6...

result:

wrong answer 53rd numbers differ - expected: '2', found: '3'