Submission #846352

#	Time	Username	Problem	Language	Result	Execution time	Memory
846352		vjudge1	ČVENK (COI15_cvenk)	C++17	22 / 100	91 ms	31568 KiB

cvenk

#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int32_t main(){
  //freopen("in.txt","r", stdin);
  int n;
  cin>>n;
  vector<array<int, 2> > a(n);
  for(int i = 0; i < n; i++){
    cin>>a[i][0]>>a[i][1];
  }

  if(n == 2){
    array<int, 2> f = a[0];
    array<int, 2> s = a[1];
    int mxbt1, mxbt2;
    for(int k = 29; k >= 0; k--){
        if((1 << k)&(f[0]|f[1])){
            mxbt1 = k;
            break;
        }
    }
    for(int k = 29; k >= 0; k--){
        if((1 << k)&(s[0]|s[1])){
            mxbt2 = k;
            break;
        }
    }

    if(f == s){
        cout<<0<<endl;
        return 0;
    }

    int mnbt = 0;
    int ans = 0;

    while((f[0] != s[0] && f[1] != s[1]) && mnbt < 30){
      if(f[0]&(1 << mnbt) && mnbt < mxbt1){
         ans += (1 << mnbt);
         f[0] -= (1 << mnbt);
      }
      if(f[1]&(1 << mnbt) && mnbt < mxbt1){
         ans += (1 << mnbt);
         f[1] -= (1 << mnbt);
      }
      if(s[0]&(1 << mnbt) && mnbt < mxbt2){
         ans += (1 << mnbt);
         s[0] -= (1 << mnbt);
      }
      if(s[1]&(1 << mnbt) && mnbt < mxbt2){
         ans += (1 << mnbt);
         s[1] -= (1 << mnbt);
      }

      mnbt++;
    }

    cout<<abs(f[0] - s[0]) + abs(f[1] - s[1]) + ans<<endl;

    return 0;
  }

  vector<vector<vector<int> > > go(500, vector<vector<int> >(500, vector<int>(2)));
  int sum = 0, mxx = 0, mxy = 0;
  for(int i = 0; i < n; i++){
    int x = a[i][0], y = a[i][1];
    sum = (sum + x + y);
    mxx = max(mxx, x);
    mxy = max(mxy, y);

    while(x > 0 || y > 0){
        if(x == 0){
            go[x][y-1][1]++;
            y--;
        }
        else if(y == 0){
            go[x-1][y][0]++;
            x--;
        }
        else if((x-1)&y){
            go[x][y-1][1]++;
            y--;
        }
        else{
            go[x-1][y][0]++;
            x--;
        }
    }
  }

  int ans = sum;
  queue<array<int, 3> > q;
  q.push({0, 0, sum});
  while(!q.empty()){
    int x = q.front()[0], y = q.front()[1], val = q.front()[2];
    q.pop();
    ans = min(ans, val);

    if(!((x+1)&y) && x < mxx){
        q.push({x+1, y, val - go[x][y][0] + (n - go[x][y][0])});
    }
    if(!(x&(y+1)) && y < mxy){
        q.push({x, y+1, val - go[x][y][1] + (n - go[x][y][1])});
    }
  }

  cout<<ans<<endl;
  return 0;
}

Compilation message (stderr)

cvenk.cpp: In function 'int32_t main()':
cvenk.cpp:54:27: warning: 'mxbt2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |       if(s[0]&(1 << mnbt) && mnbt < mxbt2){
cvenk.cpp:46:27: warning: 'mxbt1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |       if(f[0]&(1 << mnbt) && mnbt < mxbt1){

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 22 / 22
• Subtask 4: 0 / 40