| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 805010 |
2023-08-03T12:25:57 Z |
moe_solution(#10139) |
Shifty Grid (CCO17_shifty) |
C++17 |
|
396 ms |
1048576 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using ull=unsigned long long;
using db=long double;
using pii=array<int,2>;
using pll=array<ll,2>;
using pdb=array<db,2>;
using tii=array<int,3>;
using tll=array<ll,3>;
using tdb=array<db,3>;
using ti4=array<int,4>;
using tl4=array<ll,4>;
using td4=array<db,4>;
//using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<> gen(1,100);
template <int MOD_> struct modnum{
private:
int v;
public:
static const int MOD = MOD_;
modnum() : v(0) {}
modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int () const { return v; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
modnum& operator += (const modnum& o) {
v += o.v;
if (v >= MOD) v -= MOD;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
if (v < 0) v += MOD;
return *this;
}
modnum& operator *= (const modnum& o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
friend modnum pow(modnum a, ll p) {
modnum ans = 1;
for (; p; p /= 2, a *= a) if (p&1) ans *= a;
return ans;
}
modnum operator ~ () const {
modnum res;
res.v = pow((modnum)v, MOD - 2).v;
return res;
}
modnum& operator /= (const modnum& o) {
return *this *= (~o);
}
modnum operator-() const { return modnum(-v); }
modnum& operator++() { return *this += 1; }
modnum operator++(int){ modnum tmp=*this; ++*this; return tmp; }
modnum& operator--() { return *this -= 1; }
modnum operator--(int){ modnum tmp=*this; --*this; return tmp; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
friend ostream& operator<<(std::ostream& os, const modnum& o)
{
os << o.v;
return os;
}
friend istream& operator>>(std::istream& is, modnum& o)
{
is >> o.v;
return is;
}
};
const ll mod=998244353,inf=1e18;
const int N=105;
using mi=modnum<mod>;
int n,m,a[N][N],b[N][N];
pii inv[N*N];
vector<tii> ans;
void output(string s=""){
cout<<s<<endl;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cout<<a[i][j]<<" \n"[j==m-1];
}
void rMove(int i,int r){
r+=n*m;
r%=m;
if(!r) return;
ans.push_back({1,i+1,r});
for(int j=0;j<m;j++) b[i][(j+r)%m]=a[i][j];
for(int j=0;j<m;j++){
a[i][j]=b[i][j];
inv[a[i][j]]={i,j};
}
}
void cMove(int j,int c){
c+=n*m;
c%=n;
if(!c) return;
ans.push_back({2,j+1,c});
for(int i=0;i<n;i++) b[(i+c)%n][j]=a[i][j];
for(int i=0;i<n;i++){
a[i][j]=b[i][j];
inv[a[i][j]]={i,j};
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
cin>>n>>m;
vector<int> v(n*m);
for(int i=0;i<n*m;i++) v[i]=i;
shuffle(v.begin(),v.end(),rng);
int p=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=v[p++];
cin>>a[i][j];
b[i][j]=a[i][j];
inv[a[i][j]]={i,j};
}
}
//output("Start");
// Step 1
for(int i=0;i<n-1;i++){
for(int j=0;j<m-1;j++){
auto [x,y]=inv[(n-2-i)*m+j];
rMove(x,m-1-y);
cMove(m-1,n-1-x);
if(x!=n-1) rMove(x,y+1);
rMove(n-1,j+1);
cMove(j,1);
//output("Step "+to_string(i)+" "+to_string(j));
}
//output("Step "+to_string(i));
}
//output("After Step 1");
uniform_int_distribution<> gen1(0,m-1);
uniform_int_distribution<> gen2(0,n-1);
do{
for(int t=0;t<100;t++){
rMove(n-1,gen1(rng));
cMove(m-1,gen2(rng));
}
// Step 2
for(int j=0;j<m;j++){
auto [x,y]=inv[(n-1)*m+j];
if(x!=n-1){
rMove(n-1,j);
cMove(m-1,n-1-x);
}
rMove(n-1,m-1-y);
cMove(m-1,1);
if(j) rMove(n-1,m-2-inv[(n-1)*m+j-1][1]);
cMove(m-1,n-1);
}
//output("After Step 2");
// Step 3
for(int i=0;i<n;i++){
int x=inv[m*i+m-1][0];
if(!i){
cMove(m-1,n-x);
continue;
}
if(x==i) continue;
cMove(m-1,n-1-x);
rMove(n-1,m/2);
int v=a[n-1][m-1];
x=inv[m*(i-1)+m-1][0];
cMove(m-1,n-2-x);
rMove(n-1,m/2);
x=inv[v][0];
cMove(m-1,n-1-x);
rMove(n-1,m/2);
x=inv[m-1][0];
cMove(m-1,n-x);
//output(to_string(i));
}
//output("After Step 3");
}while(a[n-1][0]!=(n-1)*m);
cout<<ans.size()<<"\n";
for(auto [x,y,z]: ans) cout<<x<<" "<<y<<" "<<z<<"\n";
//output("Result");
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:126:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen("input.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | freopen("output.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
396 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
396 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
