Submission #924807

#	Time	Username	Problem	Language	Result	Execution time	Memory
924807		gs25	Shifty Grid (CCO17_shifty)	C++17	25 / 25	135 ms	2256 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, n) for (int i = 1; i <= n; ++i)
#define ff first
#define ss second
using namespace std;
typedef long long ll;

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = [";    \
  _print(x);                                                                   \
  cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

//#define int ll 

typedef pair<int,int> pi; 

pi pos[100000]; 
int a[102][102]; 
int N,M; 

#define mp make_pair

vector<tuple<int,int,int>> ans; 

void print_(){
	rep(i,N){
		rep(j,M) cout << a[i][j] << " \n"[j==M-1]; 
	}
}

void rotate(pi x, pi y, pi z ){
	assert(x.ff == y.ff && y.ss==z.ss); 
	int vx = a[x.ff][x.ss], vy=a[y.ff][y.ss], vz = a[z.ff][z.ss]; 
	int i1 = x.ff, i2 = z.ff, j1 = x.ss, j2 = y.ss; 
	ans.pb({1,i1,(j2-j1+M)%M}); 
	ans.pb({2,j2,(i1-i2+N)%N}); 
	ans.pb({1,i1,(j1-j2+M)%M}); 
	ans.pb({2,j2,(i2-i1+N)%N}); 
	// x y z -> z x y 
	a[i1][j1] = vz; 
	a[i1][j2] = vx; 
	a[i2][j2] = vy; 
	pos[vz] = make_pair(i1,j1);//i1,j1}; 
	pos[vx] = make_pair(i1,j2);//{i1,j2}; 
	pos[vy] = make_pair(i2,j2);//{i2,j2}; 
	//cout << i1 << " " << j1 << " " << i1 << " " << j2 << " " << i2 << " " << j2 << "\n";
	//print_();
};

void solve(){
	cin >> N >> M; 
	rep(i,N){
		rep(j,M){
			int x; cin >> x;
			pos[x] = make_pair(i,j); 
			a[i][j] = x; 
		}
	}
	for(int i=0; i<=M*(N-1)-1; i++){
		dbg(i);
		int x = i/M, y = i%M, nx = pos[i].ff, ny = pos[i].ss; 
		assert(nx>=x);
		if(nx==x && ny==y) x=x; 
		else if(x==nx){
			assert(ny>=y); 
			rotate(mp(x,y),mp(x,ny),mp(x+1,ny)); 
			rotate(mp(x,y),mp(x,ny),mp(x+1,ny)); 
			//continue; 
		}
		else if(ny<y){
			rotate(mp(nx,ny),mp(nx,y),mp(x,y)); 
			rotate(mp(nx,ny),mp(nx,y),mp(x,y)); 

			//continue; 
		}
		else if(ny==y){
			int nyy = (ny+1)%M; 
			rotate(mp(nx,nyy),mp(nx,ny),mp(x,y));
			//rotate(mp(nx,nyy),mp(nx,ny),mp(x,y));
			//continue; 
		}
		else if(ny>y){
			rotate(mp(x,y),mp(x,ny),mp(nx,ny)); 
			//continue; 
		}
	}
	for(int i=M*(N-1); i<M*(N)-2; i++){
		int x = i/M, y = i%M, nx = pos[i].ff, ny = pos[i].ss; 
		dbg(i,x,y,nx,ny);
		if(ny==y) continue;
		assert(x==nx && x==N-1); 
		int z = (ny==M-1) ? M-2 : M-1; 
		rotate(mp(N-1,ny),mp(N-1,y),mp(N-2,y)); 
		rotate(mp(N-1,z),mp(N-1,y),mp(N-2,y)); 
		rotate(mp(N-1,ny),mp(N-1,y),mp(N-2,y)); 
		rotate(mp(N-1,ny),mp(N-1,y),mp(N-2,y)); 
	}
	
	// N*M-1, N*M-2; 
	if(a[N-1][M-1]!=N*M-1){
		rep(i,N-1){	
			ans.pb({2,M-1,1}); 
			ans.pb({1,N-1,1});
			ans.pb({2,M-1,N-1}); 
			ans.pb({1,N-1,M-1}); 
			ans.pb({2,M-1,1});
		}
	} 
	cout << ans.size() << "\n";
	for(auto [i,j,k] : ans) cout << i << " " << j+1 << " " << k << "\n"; 
}

int32_t main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t=1; //cin >> t; 
    while(t--) solve(); 
    
    
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10