# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
924807 |
2024-02-09T17:49:59 Z |
gs25 |
Shifty Grid (CCO17_shifty) |
C++17 |
|
135 ms |
2256 KB |
#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();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
756 KB |
Output is correct |
5 |
Correct |
1 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
124 ms |
940 KB |
Output is correct |
6 |
Correct |
116 ms |
920 KB |
Output is correct |
7 |
Correct |
119 ms |
848 KB |
Output is correct |
8 |
Correct |
117 ms |
932 KB |
Output is correct |
9 |
Correct |
126 ms |
852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
468 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
756 KB |
Output is correct |
5 |
Correct |
1 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
124 ms |
940 KB |
Output is correct |
18 |
Correct |
116 ms |
920 KB |
Output is correct |
19 |
Correct |
119 ms |
848 KB |
Output is correct |
20 |
Correct |
117 ms |
932 KB |
Output is correct |
21 |
Correct |
126 ms |
852 KB |
Output is correct |
22 |
Correct |
117 ms |
1024 KB |
Output is correct |
23 |
Correct |
119 ms |
1156 KB |
Output is correct |
24 |
Correct |
118 ms |
836 KB |
Output is correct |
25 |
Correct |
119 ms |
1020 KB |
Output is correct |
26 |
Correct |
122 ms |
932 KB |
Output is correct |
27 |
Correct |
117 ms |
840 KB |
Output is correct |
28 |
Correct |
135 ms |
2228 KB |
Output is correct |
29 |
Correct |
129 ms |
2220 KB |
Output is correct |
30 |
Correct |
128 ms |
2248 KB |
Output is correct |
31 |
Correct |
129 ms |
2252 KB |
Output is correct |
32 |
Correct |
131 ms |
2256 KB |
Output is correct |
33 |
Correct |
24 ms |
860 KB |
Output is correct |
34 |
Correct |
25 ms |
800 KB |
Output is correct |
35 |
Correct |
6 ms |
604 KB |
Output is correct |
36 |
Correct |
91 ms |
1808 KB |
Output is correct |
37 |
Correct |
22 ms |
784 KB |
Output is correct |
38 |
Correct |
28 ms |
856 KB |
Output is correct |
39 |
Correct |
25 ms |
860 KB |
Output is correct |
40 |
Correct |
53 ms |
1100 KB |
Output is correct |
41 |
Correct |
25 ms |
856 KB |
Output is correct |
42 |
Correct |
26 ms |
788 KB |
Output is correct |
43 |
Correct |
84 ms |
1680 KB |
Output is correct |
44 |
Correct |
17 ms |
796 KB |
Output is correct |
45 |
Correct |
65 ms |
1244 KB |
Output is correct |
46 |
Correct |
45 ms |
1488 KB |
Output is correct |