welleyth

Day 1. Ledys Piano

Jul 28th, 2021
758
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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 = 998244353;
  20. const int MAXN = (int)1e5 + 10;
  21. const int N = (int)2e5 + 111;
  22. const int debug = 0;
  23. const long double eps = 1e-7;
  24.  
  25. typedef tree<
  26. int,
  27. null_type,
  28. less_equal<int>,
  29. rb_tree_tag,
  30. tree_order_statistics_node_update>
  31. ordered_set;
  32.  
  33. int bpow(int a,int b){
  34.     if(b == 0)
  35.         return 1ll;
  36.     if(b % 2 == 0){
  37.         int t = bpow(a,b/2);
  38.         return (t * t) % md;
  39.     }
  40.     return (a * bpow(a,b-1)) % md;
  41. }
  42.  
  43. int inv(int a){ /// return 1/a by PRIME modulo md
  44.     return bpow(a,md-2);
  45. }
  46.  
  47. void myerase(ordered_set& st, int t){
  48.     int r = st.order_of_key(t);
  49.     ordered_set::iterator it = st.find_by_order(r);
  50.     st.erase(it);
  51.     return;
  52. }
  53.  
  54. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  55.  
  56. void init(){
  57.  
  58.     return;
  59. }
  60.  
  61. int t[(int)4e5+11];
  62. int a[(int)2e5+11];
  63.  
  64. void build(int v,int l,int r){
  65.     if(l > r)
  66.         return;
  67.     if(l == r){
  68.         t[v] = a[l];
  69.         return;
  70.     }
  71.     int m = (l + r) >> 1;
  72.     build(v<<1,l,m);
  73.     build(v<<1|1,m+1,r);
  74.     t[v] = __gcd(t[v<<1],t[v<<1|1]);
  75.     return;
  76. }
  77.  
  78. int get(int v,int l,int r,int tl,int tr){
  79.     if(l == tl && tr == r)
  80.         return t[v];
  81.     if(l > r || tl > tr)
  82.         return 0;
  83.     int m = (l + r) >> 1;
  84.     return __gcd(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(tl,m+1),tr));
  85. }
  86.  
  87. void solve_case(){
  88.     int c;
  89.     cin >> c;
  90.     int n;
  91.     cin >> n;
  92.  
  93.     for(int i = 0; i < n; i++){
  94.         cin >> a[i];
  95.     }
  96.  
  97.     int g = a[0];
  98.     for(int i = 0; i < n; i++){
  99.         g = __gcd(g,a[i]);
  100.     }
  101.  
  102.     if(c == 1){
  103.         cout << g * n;
  104.         return;
  105.     }
  106.  
  107.     int cnt = 0;
  108.  
  109.     for(int i = 0; i < n; i++){
  110.         a[i] /= g;
  111.         cnt += (a[i] == 1);
  112.     }
  113.  
  114.     vector<int> ans;
  115.  
  116.     if(cnt > 0){
  117.         bool upd = true;
  118.         while(upd){
  119.             upd = false;
  120.             for(int i = 0; i + 1 < n; i++){
  121.                 if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
  122.                     a[i] = a[i+1] = __gcd(a[i],a[i+1]);
  123.                     ans.pb(i+1);
  124.                     upd = true;
  125.                 }
  126.             }
  127.         }
  128.  
  129.         upd = true;
  130.         while(upd){
  131.             upd = false;
  132.             for(int i = 0; i + 1 < n; i++){
  133.                 if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 || a[i+1] != 1)){
  134.                     a[i] = a[i+1] = __gcd(a[i],a[i+1]);
  135.                     ans.pb(i+1);
  136.                     upd = true;
  137.                 }
  138.             }
  139.         }
  140.         cout << ans.size() << "\n";
  141.         for(auto x : ans)
  142.             cout << x << " ";
  143.         return;
  144.     }
  145.  
  146.     build(1,0,n-1);
  147.  
  148.     int tl,tr;
  149.     tl = 0, tr = n - 1;
  150.  
  151.     for(int i = 0; i < n; i++){
  152.         if(get(1,0,n-1,i,n-1) != 1)
  153.             break;
  154.         int l = i + 1, r = n - 1;
  155.         while(l - r > 1){
  156.             int m = (l + r) >> 1;
  157.             if(get(1,0,n-1,i,m) == 1)
  158.                 r = m;
  159.             else
  160.                 l = m + 1;
  161.         }
  162.         l = (get(1,0,n-1,i,l) == 1 ? l : r);
  163.         if(tr - tl > l - i){
  164.             tr = l, tl = i;
  165.         }
  166.     }
  167.  
  168.     for(int i = tl; i < tr; i++){
  169.         a[i] = a[i+1] = __gcd(a[i],a[i+1]);
  170.         ans.pb(i+1);
  171.     }
  172.  
  173.     bool upd = true;
  174.  
  175.     while(upd){
  176.         upd = false;
  177.         for(int i = 0; i + 1 < n; i++){
  178.             if(__gcd(a[i],a[i+1]) == 1 && (a[i] != 1 && a[i+1] != 1)){
  179.                 a[i] = a[i+1] = __gcd(a[i],a[i+1]);
  180.                 ans.pb(i+1);
  181.                 upd = true;
  182.             }
  183.         }
  184.         for(int i = 0; i + 1 < n; i++){
  185.             if(__gcd(a[i],a[i+1]) == 1 && a[i] != a[i+1]){
  186.                 a[i] = a[i+1] = __gcd(a[i],a[i+1]);
  187.                 ans.pb(i+1);
  188.                 upd = true;
  189.             }
  190.         }
  191.     }
  192.  
  193.     cout << ans.size() << "\n";
  194.     for(auto x : ans){
  195.         cout << x << " ";
  196.     }
  197.  
  198.     return;
  199. }
  200.  
  201. signed main(){
  202.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  203. //    freopen("input.txt","r",stdin);
  204. //    freopen("output.txt","w",stdout);
  205.  
  206.     init();
  207.  
  208.     int tests = 1;
  209. //    cin >> tests;
  210.  
  211.     for(int _ = 1; _ <= tests; _++){
  212. //        n = _;
  213.         solve_case();
  214.     }
  215.  
  216.     return 0;
  217. }
  218.  
  219. /*
  220.  
  221. max(a[i],a[i+1],a[i+2]) - min(a[i],a[i+1],a[i+2])
  222.  
  223. -2 * a[i] - 2 * a[i+1] - 2 * a[i+2]
  224.  
  225. 1
  226. 9
  227. 1 2
  228. 1 3
  229. 2 4
  230. 2 5
  231. 3 6
  232. 3 7
  233. 1 8
  234. 6 9
  235.  
  236. */
  237.  
RAW Paste Data