Submission #3566823

---

Source Code Expand

#include <iostream>
#include <cassert>
#include <vector>
#include <random>
using namespace std;
typedef pair<int,int> P;
int N = 30,A[31][31],D[900] = {0};
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1},visited[31][31] = {{0}};
vector<P> ans,route;
mt19937 mt{random_device{}()};
uniform_int_distribution<int> rd(0,3);

void print(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			cout << A[i][j] << (j!=N? " ":"\n");
		}
	}
}

bool in(int x,int y){
	return 1<=x && x<=N && 1<=y && y<=N;
}

vector<P> make_route(int x,int y){
	int px = x,py = y;
	visited[x][y] = 1;
	vector<P> res;
	res.push_back({x,y});
	for(int i=2;i<=N*N;i++){
		int k = 0,nx = px,ny = py;
		while(!in(nx,ny) || visited[nx][ny]==1){
			k = rd(mt); nx = px+dx[k],ny = py+dy[k];
		}
		res.push_back({nx,ny}); visited[nx][ny] = 1; px = nx; py = ny;
	}
	return res;
}

/*void init(){
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++) visited[i][j] = 0;
	}
}

vector<P> longest(int x,int y,vector<P> v){
	visited[x][y] = 1;
	v.push_back({x,y});
	vector<P> result = v;
	if(A[x][y]==1) return result;
	for(int k=0;k<4;k++){
		int nx = x+dx[k],ny = y+dy[k];
		if(!in(nx,ny)) continue;
		if(A[x][y]-1==A[nx][ny]){
			vector<P> u = longest(nx,ny,v);
			if(result.size()<u.size()){
				result = u;
				assert(result==u);
			}
		}
	}
	return result;
}
*/
int main(){
	int x,y,ma = 0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N;j++){
			cin >> A[i][j];
			if(A[i][j]>ma){
				ma = A[i][j];
				x = i; y = j;
			}
		}
	}
	route = make_route(x,y);
	for(int i=0;i<N*N;i++){
		if(i!=0) D[i] = max(0,A[route[i].first][route[i].second]-A[route[i-1].first][route[i-1].second]+1);
		else D[i] = A[route[i].first][route[i].second];
	}
	for(int i=N*N-1;i>=0;i--){
		int c = 0;
		x = route[i].first; y = route[i].second;
		while(c<D[i]){
			ans.push_back({x,y});
			A[x][y]--; c++;
			for(int k=i+1;k<=N;k++){
				if(A[route[k-1].first][route[k-1].second]!=0 && A[route[k-1].first][route[k-1].second]==A[route[k].first][route[k].second]){
					ans.push_back({route[k].first,route[k].second});
					A[route[k].first][route[k].second]--;
				}
			}
		}
	}
	for(int i=0;i<ans.size();i++){
		cout << ans[i].first << " " << ans[i].second << endl;
	}
}

Submission Info

Judge Result