Advertisement
welleyth

C.

Feb 8th, 2022
1,084
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define pb push_back
  9. #define int long long
  10. #define uint __int128
  11. #define mp make_pair
  12. #define left left_compile
  13. #define right right_compile
  14.  
  15. #pragma GCC optimize("O3")
  16. #pragma GCC optimize("unroll-loops")
  17.  
  18. const int INF = (int)1e18;
  19. const int md = (int)1e18 + 7;
  20. const int MAXN = (int)1e6 + 111;
  21. const int N = (int)2e5 + 111;
  22. //const int L = 20;
  23. const int debug = 0;
  24. const long double eps = 0.0001;
  25. //const int P[2] = {29,31};
  26.  
  27. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  28.  
  29. struct DSU{
  30.     int n;
  31.     vector<int> parent;
  32.     vector<int> sz;
  33.     vector<int> deep;
  34.     vector<int> l,r;
  35.     DSU(int nn){
  36.         n = nn;
  37.         parent.resize(n+1);
  38.         sz.resize(n+1,1);
  39.         deep.resize(n+1,1);
  40.         l.resize(n+1);
  41.         r.resize(n+1);
  42.         for(int i = 0; i <= n; i++)
  43.             parent[i] = i, sz[i] = 1, deep[i] = 1, l[i] = r[i] = i;
  44.     }
  45.     int find_parent(int x){
  46.         if(parent[x] == x)
  47.             return x;
  48.         return parent[x] = find_parent(parent[x]);
  49.     }
  50.     bool union_sets(int a,int b){
  51.         int A,B;
  52.         A = a, B = b;
  53.         if(A == B)
  54.             return true;
  55.         a = find_parent(a);
  56.         b = find_parent(b);
  57.         if(a == b)
  58.             return false;
  59.         parent[a] = b;
  60. //        cerr << A << " " << B << "\n";
  61. //        cerr << l[a] << " " << r[a] << "\n";
  62. //        cerr << l[b] << " " << r[b] << "\n\n";
  63.         if(l[a] == A && l[b] == B)
  64.             l[b] = r[b], r[b] = r[a];
  65.         else if(l[a] == A && r[b] == B)
  66.             l[b] = l[b], r[b] = r[a];
  67.         else if(r[a] == A && l[b] == B)
  68.             l[b] = l[a], r[b] = r[b];
  69.         else if(r[a] == A && r[b] == B)
  70.             r[b] = l[b], l[b] = l[a];
  71.         else
  72.             return false;
  73.         return true;
  74.     }
  75.     bool connected(int a,int b){
  76.         return find_parent(a) == find_parent(b);
  77.     }
  78. };
  79.  
  80.  
  81. template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  82. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  83.  
  84. int bpow(int a,int b){
  85.     if(b <= 0)
  86.         return 1ll;
  87.     if(b % 2 == 0){
  88.         int t = bpow(a,b/2) % md;
  89.         return (t * t) % md;
  90.     }
  91.     return (a * bpow(a,b-1)) % md;
  92. }
  93.  
  94. int inv(int a){ /// return 1/a by PRIME modulo md
  95.     return bpow(a,md-2);
  96. }
  97.  
  98. template<class T>
  99. void myerase(ordered_multiset<T>& st, T t){
  100.     T r = st.order_of_key(t);
  101.     typename ordered_multiset<T>::iterator it = st.find_by_order(r);
  102.     st.erase(it);
  103.     return;
  104. }
  105.  
  106. int fac[555555];
  107. int invfac[555555];
  108.  
  109. void init(){
  110.     fac[0] = 1;
  111.     invfac[0] = 1;
  112.  
  113.     for(int i = 1; i < 555555; i++){
  114.         fac[i] = fac[i-1] * i;
  115.         invfac[i] = inv(fac[i]);
  116.     }
  117.  
  118.     return;
  119. }
  120.  
  121. //void add(int& a,int b){
  122. //    a = (a + b >= md ? a + b - md : a + b);
  123. //}
  124. //
  125. //void sub(int& a,int b){
  126. //    a = (a < b ? a - b + md : a - b);
  127. //}
  128.  
  129. int mult(int a,int b){
  130.     return a * b % md;
  131. }
  132.  
  133. int C(int n,int k){
  134.     assert(k >= 0 && k <= n);
  135.     return mult(fac[n],mult(invfac[n-k],invfac[k]));
  136. }
  137.  
  138. const int DX[] = {1,0,-1,0};
  139. const int DY[] = {0,1,0,-1};
  140.  
  141. void solve(){
  142.     int n,m;
  143.     cin >> n >> m;
  144.  
  145.     if(n == 1 && m == 1){
  146.         cout << "1\n1\n";
  147.         return;
  148.     }
  149.  
  150.     if(n == 1){
  151.         if(m % 2 == 1){
  152.             cout << "3\n";
  153.             for(int i = 0; i < m - 1; i++){
  154.                 cout << i % 2 + 1 << " ";
  155.             }
  156.             cout << "3\n";
  157.         } else {
  158.             cout << "2\n";
  159.             for(int i = 0; i < m; i++){
  160.                 cout << i % 2 + 1 << " ";
  161.             }
  162.             cout << "\n";
  163.         }
  164.         return;
  165.     }
  166.  
  167.     if(m == 1){
  168.         if(n % 2 == 1){
  169.             cout << "3\n";
  170.             for(int i = 0; i < n - 1; i++){
  171.                 cout << i % 2 + 1 << "\n";
  172.             }
  173.             cout << "3\n";
  174.         } else {
  175.             cout << "2\n";
  176.             for(int i = 0; i < n; i++){
  177.                 cout << i % 2 + 1 << "\n";
  178.             }
  179.         }
  180.         return;
  181.     }
  182.  
  183.     if(n % 2 == 0 && m % 2 == 0){
  184.         cout << "2\n";
  185.         for(int i = 0; i < n; i++){
  186.             for(int j = 0; j < m; j++){
  187.                 cout << (i + j) % 2 + 1 << " ";
  188.             }
  189.             cout << "\n";
  190.         }
  191.         return;
  192.     }
  193.  
  194.     cout << "3\n";
  195.  
  196.     for(int i = 1; i < n; i++){
  197.         if(i % 2 == 0){
  198.             cout << "3";
  199.             for(int j = 1; j < m; j++){
  200.                 if(j % 2 == 1)
  201.                     cout << " 1";
  202.                 else
  203.                     cout << " 2";
  204.             }
  205.         } else {
  206.             cout << "2";
  207.             for(int j = 1; j < m; j++){
  208.                 if(j % 2 == 1)
  209.                     cout << " 3";
  210.                 else
  211.                     cout << " 1";
  212.             }
  213.         }
  214.         cout << "\n";
  215.     }
  216.  
  217.     cout << "1";
  218.     for(int j = 1; j < m; j++){
  219.         if(j % 2 == 1)
  220.             cout << " 2";
  221.         else
  222.             cout << " 3";
  223.     }
  224.     cout << "\n";
  225.  
  226.     return;
  227. }
  228.  
  229. /**
  230. 7 7 7 0 2
  231.  
  232.  
  233. 4 4
  234. 1 2 1 2
  235. 2 1 2 1
  236. 1 2 1 2
  237. 2 1 2 1
  238.  
  239. n > 2 m > 2
  240. 3 1 2 1 2
  241. 2 3 1 3 1
  242. 3 1 2 1 2
  243. 1 2 3 2 3
  244.  
  245. n == 1
  246.  
  247. 1 2 1 2 1 2
  248.  
  249.  
  250. **/
  251.  
  252. signed main(){
  253.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  254.  
  255. //    init();
  256.  
  257.     int tests = 1;
  258. //    cin >> tests;
  259.  
  260.     for(int _ = 1; _ <= tests; _++){
  261.         solve();
  262.     }
  263. //
  264. //    #ifdef __WIN32
  265. //        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  266. //    #endif
  267.  
  268.     return 0;
  269. }
  270. /**
  271.  
  272.  
  273. **/
  274.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement