Korotkodul

регион B debug

Jul 21st, 2022 (edited)
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17.     for (auto x: v) cout<<x<<' ';
  18.     cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22.     for (auto x: v) cout<<x<<' ';
  23.     cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28.     for (auto x: v) cv(x);
  29.     cout<<"\n";
  30. }
  31.  
  32. void cvb(vector <bool> v){
  33.     for (bool x: v) cout<<x<<' ';
  34.     cout<<"\n";
  35. }
  36.  
  37. void cvs(vector <string>  v){
  38.     for (auto a: v){
  39.         cout<<a<<"\n";
  40.     }
  41. }
  42.  
  43.  
  44. struct res{
  45.     ll dif;
  46.     char D;
  47.     int crd;
  48. };
  49.  
  50.  
  51. bool cmp(res a, res b){//for y
  52.     return (a.dif < b.dif) || ( (a.dif == b.dif) && (a.crd < b.crd) );
  53. }
  54.  
  55.  
  56. ll S(ll a1, ll d, ll n){
  57.     return (2*a1 + d * (n - 1)) * n / 2;
  58. }
  59.  
  60.  
  61.  
  62.  
  63. bool sh = 1;
  64.  
  65.  
  66. void bs(int m){
  67.     ll to = S(1,1,m) / 2;
  68.     int L = 0, R = -1,M;
  69.     //L,R - ans + потос check перебор
  70.     while (L + 1 < R){
  71.         M = (L + R) / 2;
  72.         ll y = S(1, 1, M);
  73.         if (y < to){
  74.             L = M;
  75.         }
  76.         else{
  77.             R = M;
  78.         }
  79.     }
  80.     int yres;
  81.     if (abs(S(1,1,m) - 2*S(1,1,L)) < abs(S(1,1,m) - 2*S(1,1,R)) ){
  82.         yres=L;
  83.     }
  84.     else{
  85.         yres=R;
  86.     }
  87.  
  88.     cout<<'V'<<' '<<(yres+1)<<"\n";
  89. }
  90.  
  91. int main()
  92. {
  93.     ios::sync_with_stdio(0);
  94.     cin.tie(0);
  95.     cout.tie(0);
  96.     int n,m,t=1;
  97.     if (!sh) cin>>t;
  98.     for (int go=0;go<t;++go){
  99.         cin>>n>>m;
  100.         if (n == 1){
  101.             bs(m);
  102.             continue;
  103.         }
  104.         //res ans;
  105.  
  106.         vector <ll> Ox(n), Oy(m), pfx(n), pfy(m);
  107.         for (int i = 0; i < n; ++i){
  108.             Ox[i] = S(i*m + 1, 1, m);
  109.         }
  110.         pfx[0] = Ox[0];
  111.         for (int i=1;i<n;++i){
  112.             pfx[i] = pfx[i-1] + Ox[i];
  113.         }
  114.  
  115.         for (int i=0;i<m;++i){
  116.             Oy[i] = S(i+1, m, n);
  117.         }
  118.         pfy[0] = Oy[0];
  119.         for (int i=1;i<m;++i){
  120.             pfy[i] = pfy[i-1] + Oy[i];
  121.         }
  122.         //cout<<"sh = "<<sh<<"\n";
  123.         /*if (sh){
  124.             //cout<<"FF\n";
  125.             //cout<<"n m = "<<n<<' '<<m<<"\n";
  126.             for (int i = 0; i < n; ++i){
  127.                 for (int j = i*m + 1; j <= m*(i+1); ++j){
  128.                     cout<<j<<' ';
  129.                 }cout<<"\n";
  130.             }cout<<"\n";
  131.         }*/
  132.  
  133.         vector <res> varX, varY;
  134.         //Ox
  135.         for (int i=0;i<n-1;++i){
  136.             varX.push_back({abs( pfx[n-1] - pfx[i] * 2 ), 'H', i+2});
  137.         }
  138.  
  139.         //Oy
  140.         for (int i = 0;i<m-1;++i){
  141.             varY.push_back({abs( pfy[m-1] - pfy[i] * 2 ), 'V', i+2});
  142.         }
  143.  
  144.         sort(varX.begin(), varX.end(), cmp);
  145.         sort(varY.begin(), varY.end(), cmp);
  146.  
  147.         if (sh){
  148.             if (n>1){
  149.                 cout<<"Ox\n";
  150.                 bool ok=1;
  151.                 for (int i = 1; i < n; ++i){
  152.                     if (Ox[i] < Ox[i-1] || Ox[i] < 0){
  153.                         ok=0;
  154.                         cout<<"BAD i = "<<i<<"\n";
  155.                         cout<<"Ox[i - 1] Ox[i] = "<<Ox[i - 1]<<' '<<Ox[i]<<"\n";
  156.                     }
  157.                 }
  158.                 if (ok){
  159.                     cout<<"Ox OK\n";
  160.                 }
  161.                 cout<<"\n";
  162.  
  163.                 cout<<"pfx[n-1] = pfy[m-1] = "<<pfx[n-1]<<" = "<<pfy[m-1]<<"\n";
  164.             }
  165.  
  166.             /*if (m > 1){
  167.                 cout<<"Oy\n";
  168.                 bool ok = 1;
  169.                 for (int )
  170.             }*/
  171.         }
  172.  
  173.         if (n == 1){
  174.             cout<<'V'<<' '<<varY[0].crd<<"\n";
  175.         }
  176.         else if (m == 1){//1*1 - ?
  177.             cout<<'H'<<' '<<varX[0].crd<<"\n";
  178.         }
  179.         else if (varY[0].dif <= varX[0].dif){
  180.  
  181.             cout<<'V'<<' '<<varY[0].crd<<"\n";
  182.  
  183.             if (sh){
  184.                 cout<<"pfx[n-1] = "<<pfx[n-1]<<" = "<<pfy[m-1]<<"\n";
  185.  
  186.                 cout<<"pfy[ varY[0].crd - 2 ] = "<<pfy[ varY[0].crd - 2 ]<<"\n";
  187.                 cout<<"pfy[m - 1] -  pfy[ varY[0].crd - 2 ] = "<<(pfy[m - 1] -  pfy[ varY[0].crd - 2 ])<<"\n";
  188.                 cout<<"dif = "<<abs(pfy[m - 1] - 2 * pfy[ varY[0].crd - 2 ])<<"\n";
  189.             }
  190.         }
  191.         else {
  192.             cout<<'H'<<' '<<varX[0].crd<<"\n";
  193.  
  194.             if (sh){
  195.  
  196.  
  197.                 cout<<"pfx[ varX[0].crd - 2 ] = "<<pfx[ varX[0].crd - 2 ]<<"\n";
  198.                 cout<<"pfx[m - 1] -  pfx[ varX[0].crd - 2 ] = "<<(pfx[m - 1] -  pfx[ varX[0].crd - 2 ])<<"\n";
  199.                 cout<<"dif = "<<abs(pfx[m - 1] - 2 * pfx[ varX[0].crd - 2 ])<<"\n";
  200.             }
  201.         }
  202.  
  203.     }
  204. }
  205. /*
  206. 1 3
  207.  
  208.  
  209. Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть,
  210. а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.
  211.  
  212.  
  213. 1 2000 2000
  214. H 642
  215.  
  216. 10000000 10000000
  217. */
  218.  
Add Comment
Please, Sign In to add comment