| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 924770 |
2024-02-09T16:07:54 Z |
gs25 |
Shifty Grid (CCO17_shifty) |
C++17 |
|
123 ms |
1112 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,(i2-i1+N)%N});
ans.pb({1,i1,(j1-j2+M)%M});
ans.pb({2,j2,(i1-i2+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));
//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({1,N-1,M-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});
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 |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Contestant's solution is invalid |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
117 ms |
696 KB |
Output is correct |
| 6 |
Incorrect |
123 ms |
1112 KB |
Contestant's solution is invalid |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Contestant's solution is invalid |
| 3 |
Halted |
0 ms |
0 KB |
- |
