Facebook
From Mammoth Sheep, 2 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 11
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll=long long;
  5. //#define int ll
  6.  
  7. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
  8. #define rep(i,b) rng(i,0,b)
  9. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
  10. #define per(i,b) gnr(i,0,b)
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define a first
  14. #define b second
  15. #define bg begin()
  16. #define ed end()
  17. #define all(x) x.bg,x.ed
  18. #define si(x) int(x.size())
  19. #ifdef LOCAL
  20. #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
  21. #else
  22. #define dmp(x) void(0)
  23. #endif
  24.  
  25. template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
  26. template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
  27.  
  28. template<class t> using vc=vector<t>;
  29. template<class t> using vvc=vc<vc<t>>;
  30.  
  31. using pi=pair<int,int>;
  32. using vi=vc<int>;
  33.  
  34. template<class t,class u>
  35. ostream& operator<<(ostream& os,const pair<t,u>& p){
  36.         return os<<"{"<<p.a<<","<<p.b<<"}";
  37. }
  38.  
  39. template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
  40.         os<<"{";
  41.         for(auto e:v)os<<e<<",";
  42.         return os<<"}";
  43. }
  44.  
  45. #define mp make_pair
  46. #define mt make_tuple
  47. #define one(x) memset(x,-1,sizeof(x))
  48. #define zero(x) memset(x,0,sizeof(x))
  49. #ifdef LOCAL
  50. void dmpr(ostream&os){os<<endl;}
  51. template<class T,class... Args>
  52. void dmpr(ostream&os,const T&t,const Args&... args){
  53.         os<<t<<" ";
  54.         dmpr(os,args...);
  55. }
  56. #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
  57. #else
  58. #define dmp2(...) void(0)
  59. #endif
  60.  
  61. using uint=unsigned;
  62. using ull=unsigned long long;
  63.  
  64. template<class t,size_t n>
  65. ostream& operator<<(ostream&os,const array<t,n>&a){
  66.         return os<<vc<t>(all(a));
  67. }
  68.  
  69. template<int i,class T>
  70. void print_tuple(ostream&,const T&){
  71. }
  72.  
  73. template<int i,class T,class H,class ...Args>
  74. void print_tuple(ostream&os,const T&t){
  75.         if(i)os<<",";
  76.         os<<get<i>(t);
  77.         print_tuple<i+1,T,Args...>(os,t);
  78. }
  79.  
  80. template<class ...Args>
  81. ostream& operator<<(ostream&os,const tuple<Args...>&t){
  82.         os<<"{";
  83.         print_tuple<0,tuple<Args...>,Args...>(os,t);
  84.         return os<<"}";
  85. }
  86.  
  87. template<class t>
  88. void print(t x,int suc=1){
  89.         cout<<x;
  90.         if(suc==1)
  91.                 cout<<"\n";
  92.         if(suc==2)
  93.                 cout<<" ";
  94. }
  95.  
  96. ll read(){
  97.         ll i;
  98.         cin>>i;
  99.         return i;
  100. }
  101.  
  102. vi readvi(int n,int off=0){
  103.         vi v(n);
  104.         rep(i,n)v[i]=read()+off;
  105.         return v;
  106. }
  107.  
  108. pi readpi(int off=0){
  109.         int a,b;cin>>a>>b;
  110.         return pi(a+off,b+off);
  111. }
  112.  
  113. template<class t,class u>
  114. void print(const pair<t,u>&p,int suc=1){
  115.         print(p.a,2);
  116.         print(p.b,suc);
  117. }
  118.  
  119. template<class T>
  120. void print(const vector<T>&v,int suc=1){
  121.         rep(i,v.size())
  122.                 print(v[i],i==int(v.size())-1?suc:2);
  123. }
  124.  
  125. string readString(){
  126.         string s;
  127.         cin>>s;
  128.         return s;
  129. }
  130.  
  131. template<class T>
  132. T sq(const T& t){
  133.         return t*t;
  134. }
  135.  
  136. //#define CAPITAL
  137. void yes(bool ex=true){
  138.         #ifdef CAPITAL
  139.         cout<<"YES"<<"\n";
  140.         #else
  141.         cout<<"Yes"<<"\n";
  142.         #endif
  143.         if(ex)exit(0);
  144.         #ifdef LOCAL
  145.         cout.flush();
  146.         #endif
  147. }
  148. void no(bool ex=true){
  149.         #ifdef CAPITAL
  150.         cout<<"NO"<<"\n";
  151.         #else
  152.         cout<<"No"<<"\n";
  153.         #endif
  154.         if(ex)exit(0);
  155.         #ifdef LOCAL
  156.         cout.flush();
  157.         #endif
  158. }
  159. void possible(bool ex=true){
  160.         #ifdef CAPITAL
  161.         cout<<"POSSIBLE"<<"\n";
  162.         #else
  163.         cout<<"Possible"<<"\n";
  164.         #endif
  165.         if(ex)exit(0);
  166.         #ifdef LOCAL
  167.         cout.flush();
  168.         #endif
  169. }
  170. void impossible(bool ex=true){
  171.         #ifdef CAPITAL
  172.         cout<<"IMPOSSIBLE"<<"\n";
  173.         #else
  174.         cout<<"Impossible"<<"\n";
  175.         #endif
  176.         if(ex)exit(0);
  177.         #ifdef LOCAL
  178.         cout.flush();
  179.         #endif
  180. }
  181.  
  182. constexpr ll ten(int n){
  183.         return n==0?1:ten(n-1)*10;
  184. }
  185.  
  186. const ll infLL=LLONG_MAX/3;
  187.  
  188. #ifdef int
  189. const int inf=infLL;
  190. #else
  191. const int inf=INT_MAX/2-100;
  192. #endif
  193.  
  194. int topbit(signed t){
  195.         return t==0?-1:31-__builtin_clz(t);
  196. }
  197. int topbit(ll t){
  198.         return t==0?-1:63-__builtin_clzll(t);
  199. }
  200. int botbit(signed a){
  201.         return a==0?32:__builtin_ctz(a);
  202. }
  203. int botbit(ll a){
  204.         return a==0?64:__builtin_ctzll(a);
  205. }
  206. int popcount(signed t){
  207.         return __builtin_popcount(t);
  208. }
  209. int popcount(ll t){
  210.         return __builtin_popcountll(t);
  211. }
  212. bool ispow2(int i){
  213.         return i&&(i&-i)==i;
  214. }
  215. ll mask(int i){
  216.         return (ll(1)<<i)-1;
  217. }
  218.  
  219. bool inc(int a,int b,int c){
  220.         return a<=b&&b<=c;
  221. }
  222.  
  223. template<class t> void mkuni(vc<t>&v){
  224.         sort(all(v));
  225.         v.erase(unique(all(v)),v.ed);
  226. }
  227.  
  228. ll rand_int(ll l, ll r) { //[l, r]
  229.         #ifdef LOCAL
  230.         static mt19937_64 gen;
  231.         #else
  232.         static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  233.         #endif
  234.         return uniform_int_distribution<ll>(l, r)(gen);
  235. }
  236.  
  237. template<class t>
  238. void myshuffle(vc<t>&a){
  239.         rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
  240. }
  241.  
  242. template<class t>
  243. int lwb(const vc<t>&v,const t&a){
  244.         return lower_bound(all(v),a)-v.bg;
  245. }
  246.  
  247. vvc<int> readGraph(int n,int m){
  248.         vvc<int> g(n);
  249.         rep(i,m){
  250.                 int a,b;
  251.                 cin>>a>>b;
  252.                 //sc.read(a,b);
  253.                 a--;b--;
  254.                 g[a].pb(b);
  255.                 g[b].pb(a);
  256.         }
  257.         return g;
  258. }
  259.  
  260. vvc<int> readTree(int n){
  261.         return readGraph(n,n-1);
  262. }
  263.  
  264. //sz: size of the matching
  265. //mt[i]: matching mate of the vertex i
  266. //VERIFY: yosupo
  267. //NEERC2018B
  268. //Petrozavodsk 2019w Day1 A
  269. struct maxmatching{
  270.         struct E{int a,b;};
  271.         const vvc<int>&g;
  272.         int n,sz;
  273.         vi p,t,mt;
  274.         vc<E> f;
  275.         int non(int v){
  276.                 return t[v]!=sz||p[v]==-1?v:(p[v]=non(p[v]));
  277.         }
  278.         void R(int a,int b){
  279.                 int d=mt[a];
  280.                 mt[a]=b;
  281.                 if(d==-1||mt[d]!=a)return;
  282.                 if(f[a].b==-1){
  283.                         mt[d]=f[a].a;
  284.                         R(f[a].a,d);
  285.                 }else{
  286.                         R(f[a].a,f[a].b);
  287.                         R(f[a].b,f[a].a);
  288.                 }
  289.         }
  290.         bool arg(int rt){
  291.                 queue<int> q;
  292.                 t[rt]=sz;
  293.                 p[rt]=-1;
  294.                 f[rt]=E{-1,-1};
  295.                 q.push(rt);
  296.                 while(!q.empty()){
  297.                         int a=q.front();q.pop();
  298.                         for(auto b:g[a]){
  299.                                 if(b==rt)continue;
  300.                                 if(mt[b]==-1){
  301.                                         mt[b]=a;
  302.                                         R(a,b);
  303.                                         return true;
  304.                                 }
  305.                                 if(t[b]==sz){
  306.                                         int x=non(a),y=non(b);
  307.                                         if(x==y)continue;
  308.                                         int z=rt;
  309.                                         while(x!=rt||y!=rt){
  310.                                                 if(y!=rt)swap(x,y);
  311.                                                 if(f[x].a==a&&f[x].b==b){
  312.                                                         z=x;
  313.                                                         break;
  314.                                                 }
  315.                                                 f[x]=E{a,b};
  316.                                                 x=non(f[mt[x]].a);
  317.                                         }
  318.                                         for(auto v:{non(a),non(b)}){
  319.                                                 while(v!=z){
  320.                                                         t[v]=sz;
  321.                                                         p[v]=z;
  322.                                                         q.push(v);
  323.                                                         v=non(f[mt[v]].a);
  324.                                                 }
  325.                                         }
  326.                                         continue;
  327.                                 }
  328.                                 if(t[mt[b]]==sz)continue;
  329.                                 f[b]=E{-1,-1};
  330.                                 t[mt[b]]=sz;
  331.                                 p[mt[b]]=b;
  332.                                 f[mt[b]]=E{a,-1};
  333.                                 q.push(mt[b]);
  334.                         }
  335.                 }
  336.                 return false;
  337.         }
  338.         maxmatching(const vvc<int>&gg):g(gg),n(g.size()),sz(0),
  339.                 p(n),t(n,-1),mt(n,-1),f(n){
  340.                 rep(i,n)if(mt[i]==-1)
  341.                         sz+=arg(i);
  342.         }
  343.         //codechef HAMILG
  344.         //res[i]=最大マッチングに必ず含まれるべき頂点なら 1, そうでないなら 0
  345.         vi need(){
  346.                 rep(i,n)if(mt[i]==-1)
  347.                         arg(i);
  348.                 vi res(n);
  349.                 rep(i,n)res[i]=(mt[i]!=-1&&t[i]!=sz);
  350.                 return res;
  351.         }
  352. };
  353.  
  354. bool adj(pi x,pi y){
  355.         auto [a,b]=x;
  356.         auto [d,e]=y;
  357.         int g=abs(a-d),h=abs(b-e);
  358.         if(g==1&&h==2)return true;
  359.         if(h==1&&g==2)return true;
  360.         return false;
  361. }
  362.  
  363. vi baka{640123342,149795075,435766641,962740521,655148792,415754176,376479654,870002679,720108329,159621518,11174811,387483131,378665771,561039471,331699185,126721473,443148615,932333129,537805256,560931851,365487476,533804022,740623840,763546631,538506276,874001638,94913828,147131095,947798556,252504454,124726188,728150503,340648925,846675740,753540696,201741433,457098100,242736752,101613178,179436008,422379147,716728797,130960454,582731547,879298814,327320790,601101480,712029853,666028075,};
  364. int seed;
  365.  
  366. using T=tuple<int,int,int>;
  367. vc<pi> dxy{};
  368. vc<T> sub(int n){
  369.         int s=0;
  370.         vvc<int> idx(n,vi(n,-1));
  371.         rep(i,n)rep(j,n){
  372.                 if(pi(i,j)==pi(0,0))continue;
  373.                 if(pi(i,j)==pi(n-1,n-1))continue;
  374.                 idx[i][j]=s++;
  375.         }
  376.         vvc<int> g(s);
  377.         rep(i,n)rep(j,n){
  378.                 if(pi(i,j)==pi(0,0))continue;
  379.                 if(pi(i,j)==pi(n-1,n-1))continue;
  380.                 for(auto [x,y]:dxy){
  381.                         x+=i;
  382.                         y+=j;
  383.                         if(inc(0,x,n-1)&&inc(0,y,n-1)){
  384.                                 if(pi(x,y)==pi(0,0))continue;
  385.                                 if(pi(x,y)==pi(n-1,n-1))continue;
  386.                                 g[idx[i][j]].pb(idx[x][y]);
  387.                         }
  388.                 }
  389.         }
  390.        
  391.         //find a cycle
  392.         vc<pi> lf;
  393.         rep(step,n/2-1){
  394.                 int x=n-1-step*2,y=step*2;
  395.                 lf.eb(x-2,y+1);
  396.                 lf.eb(x,y+2);
  397.                 lf.eb(x-1,y);
  398.                 if(step<n/2-2){
  399.                         lf.eb(x-3,y+1);
  400.                 }
  401.         }
  402.         //dmp(lf);
  403.         vi c{idx[n-1][0]};
  404.         for(auto [i,j]:lf)c.pb(idx[i][j]);
  405.         c.pb(idx[1][n-2]);
  406.         reverse(all(lf));
  407.         for(auto [i,j]:lf){
  408.                 tie(i,j)=pi(n-1-j,n-1-i);
  409.                 //dmp2(i,j);
  410.                 c.pb(idx[i][j]);
  411.         }
  412.         //dmp(idx);
  413.         rep(i,si(c)){
  414.                 int j=c[(i+1)%si(c)];
  415.                 //dmp2(i,j);
  416.                 assert(find(all(g[c[i]]),j)!=g[c[i]].ed);
  417.         }
  418.        
  419.         vc<pi> pos;
  420.         rep(i,n)rep(j,n)if(idx[i][j]!=-1)pos.eb(i,j);
  421.        
  422.         while(1){
  423.                 //int seed=rand_int(0,ten(9));
  424.                 mt19937 rnd(seed);
  425.                
  426.                 vc<bool> vis(s);
  427.                 for(auto i:c)vis[i]=true;
  428.        
  429.                 vc<T> ans;
  430.                 int cur=0;
  431.                 rep(i,si(c)){
  432.                         int v=c[i];
  433.                         vi tmp;
  434.                         while(1){
  435.                                 vis[v]=true;
  436.                                 tmp.pb(v);
  437.                                 int mn=inf;
  438.                                 vi buf;
  439.                                 for(auto j:g[v])if(!vis[j]){
  440.                                         int cnt=0;
  441.                                         for(auto k:g[j])if(!vis[k])cnt++;
  442.                                         if(mn>cnt){
  443.                                                 buf.clear();
  444.                                                 mn=cnt;
  445.                                         }
  446.                                         if(mn==cnt){
  447.                                                 buf.pb(j);
  448.                                         }
  449.                                 }
  450.                                 if(buf.empty())break;
  451.                                 v=buf[rnd()%si(buf)];
  452.                         }
  453.                         for(auto w:tmp){
  454.                                 ans.eb(pos[w].a,pos[w].b,cur);
  455.                         }
  456.                         cur^=1;
  457.                         reverse(all(tmp));
  458.                         for(auto w:tmp){
  459.                                 ans.eb(pos[w].a,pos[w].b,cur);
  460.                         }
  461.                 }
  462.  
  463.                 if(si(ans)==2*n*n-4){
  464.                         baka.pb(seed);
  465.                         return ans;
  466.                 }
  467.         }
  468. }
  469.  
  470. bool adj(T x,T y){
  471.         auto [a,b,c]=x;
  472.         auto [d,e,f]=y;
  473.         if(c!=f)return pi(a,b)==pi(d,e);
  474.         int g=abs(a-d),h=abs(b-e);
  475.         if(g==1&&h==2)return true;
  476.         if(h==1&&g==2)return true;
  477.         return false;
  478. }
  479.  
  480. void check(int n,vc<T> z){
  481.         assert(si(z)==2*n*n-4);
  482.         for(auto [a,b,c]:z){
  483.                 assert(inc(0,a,n-1));
  484.                 assert(inc(0,b,n-1));
  485.                 assert(inc(0,c,1));
  486.                 assert(pi(a,b)!=pi(0,0));
  487.                 assert(pi(a,b)!=pi(n-1,n-1));
  488.         }
  489.         rep(i,si(z)){
  490.                 assert(adj(z[i],z[(i+1)%si(z)]));
  491.         }
  492.         mkuni(z);
  493.         assert(si(z)==2*n*n-4);
  494. }
  495.  
  496. void slv(){
  497. }
  498.  
  499. signed main(){
  500.         cin.tie(0);
  501.         ios::sync_with_stdio(0);
  502.         cout<<fixed<<setprecision(20);
  503.        
  504.         rep(i,2)rep(j,2)rep(k,2){
  505.                 int a=1,b=2;
  506.                 if(i)a=-a;
  507.                 if(j)b=-b;
  508.                 if(k)swap(a,b);
  509.                 dxy.eb(a,b);
  510.         }
  511.        
  512.         /*for(int n=4;n<=100;n+=2){
  513.                 cerr<<n<<endl;
  514.                 auto ans=sub(n);
  515.                 check(n,ans);
  516.         }
  517.        
  518.         cerr<<baka<<endl;*/
  519.        
  520.         int n;cin>>n;
  521.         seed=baka[(n-4)/2];
  522.         auto ans=sub(n);
  523.         for(auto [i,j,k]:ans){
  524.                 cout<<i+1<<" "<<j+1<<" "<<k<<"\n";
  525.         }
  526. }
  527.