Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <string>
- #include <stack>
- #include <set>
- #include <map>
- #define pii pair <int,int>
- #define vec vector
- using namespace std;
- using ll = long long;
- using ld = long double;
- using db = double;
- void cv(vector <int> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvl(vector <ll> &v){
- for (auto x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvv(vector <vector <int> > &v){
- for (auto x: v) cv(x);
- cout<<"\n";
- }
- void cvb(vector <bool> v){
- for (bool x: v) cout<<x<<' ';
- cout<<"\n";
- }
- void cvs(vector <string> v){
- for (auto a: v){
- cout<<a<<"\n";
- }
- }
- struct res{
- ll dif;
- char D;
- int crd;
- };
- bool cmp(res a, res b){//for y
- return (a.dif < b.dif) || ( (a.dif == b.dif) && (a.crd < b.crd) );
- }
- ll S(ll a1, ll d, ll n){
- return (2*a1 + d * (n - 1)) * n / 2;
- }
- bool sh = 1;
- void bs(int m){
- ll to = S(1,1,m) / 2;
- int L = 0, R = -1,M;
- //L,R - ans + потос check перебор
- while (L + 1 < R){
- M = (L + R) / 2;
- ll y = S(1, 1, M);
- if (y < to){
- L = M;
- }
- else{
- R = M;
- }
- }
- int yres;
- if (abs(S(1,1,m) - 2*S(1,1,L)) < abs(S(1,1,m) - 2*S(1,1,R)) ){
- yres=L;
- }
- else{
- yres=R;
- }
- cout<<'V'<<' '<<(yres+1)<<"\n";
- }
- int main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n,m,t=1;
- if (!sh) cin>>t;
- for (int go=0;go<t;++go){
- cin>>n>>m;
- if (n == 1){
- bs(m);
- continue;
- }
- //res ans;
- vector <ll> Ox(n), Oy(m), pfx(n), pfy(m);
- for (int i = 0; i < n; ++i){
- Ox[i] = S(i*m + 1, 1, m);
- }
- pfx[0] = Ox[0];
- for (int i=1;i<n;++i){
- pfx[i] = pfx[i-1] + Ox[i];
- }
- for (int i=0;i<m;++i){
- Oy[i] = S(i+1, m, n);
- }
- pfy[0] = Oy[0];
- for (int i=1;i<m;++i){
- pfy[i] = pfy[i-1] + Oy[i];
- }
- //cout<<"sh = "<<sh<<"\n";
- /*if (sh){
- //cout<<"FF\n";
- //cout<<"n m = "<<n<<' '<<m<<"\n";
- for (int i = 0; i < n; ++i){
- for (int j = i*m + 1; j <= m*(i+1); ++j){
- cout<<j<<' ';
- }cout<<"\n";
- }cout<<"\n";
- }*/
- vector <res> varX, varY;
- //Ox
- for (int i=0;i<n-1;++i){
- varX.push_back({abs( pfx[n-1] - pfx[i] * 2 ), 'H', i+2});
- }
- //Oy
- for (int i = 0;i<m-1;++i){
- varY.push_back({abs( pfy[m-1] - pfy[i] * 2 ), 'V', i+2});
- }
- sort(varX.begin(), varX.end(), cmp);
- sort(varY.begin(), varY.end(), cmp);
- if (sh){
- if (n>1){
- cout<<"Ox\n";
- bool ok=1;
- for (int i = 1; i < n; ++i){
- if (Ox[i] < Ox[i-1] || Ox[i] < 0){
- ok=0;
- cout<<"BAD i = "<<i<<"\n";
- cout<<"Ox[i - 1] Ox[i] = "<<Ox[i - 1]<<' '<<Ox[i]<<"\n";
- }
- }
- if (ok){
- cout<<"Ox OK\n";
- }
- cout<<"\n";
- cout<<"pfx[n-1] = pfy[m-1] = "<<pfx[n-1]<<" = "<<pfy[m-1]<<"\n";
- }
- /*if (m > 1){
- cout<<"Oy\n";
- bool ok = 1;
- for (int )
- }*/
- }
- if (n == 1){
- cout<<'V'<<' '<<varY[0].crd<<"\n";
- }
- else if (m == 1){//1*1 - ?
- cout<<'H'<<' '<<varX[0].crd<<"\n";
- }
- else if (varY[0].dif <= varX[0].dif){
- cout<<'V'<<' '<<varY[0].crd<<"\n";
- if (sh){
- cout<<"pfx[n-1] = "<<pfx[n-1]<<" = "<<pfy[m-1]<<"\n";
- cout<<"pfy[ varY[0].crd - 2 ] = "<<pfy[ varY[0].crd - 2 ]<<"\n";
- cout<<"pfy[m - 1] - pfy[ varY[0].crd - 2 ] = "<<(pfy[m - 1] - pfy[ varY[0].crd - 2 ])<<"\n";
- cout<<"dif = "<<abs(pfy[m - 1] - 2 * pfy[ varY[0].crd - 2 ])<<"\n";
- }
- }
- else {
- cout<<'H'<<' '<<varX[0].crd<<"\n";
- if (sh){
- cout<<"pfx[ varX[0].crd - 2 ] = "<<pfx[ varX[0].crd - 2 ]<<"\n";
- cout<<"pfx[m - 1] - pfx[ varX[0].crd - 2 ] = "<<(pfx[m - 1] - pfx[ varX[0].crd - 2 ])<<"\n";
- cout<<"dif = "<<abs(pfx[m - 1] - 2 * pfx[ varX[0].crd - 2 ])<<"\n";
- }
- }
- }
- }
- /*
- 1 3
- Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть,
- а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.
- 1 2000 2000
- H 642
- 10000000 10000000
- */
Add Comment
Please, Sign In to add comment