oj.uz

Submission #846366

# Submission time Handle Problem Language Result Execution time Memory
846366 2023-09-07T14:03:49 Z vjudge1 ČVENK (COI15_cvenk) C++17
22 / 100
 78 ms 31568 KB 
#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 != s && mnbt < 30){
      if(s[0] == f[0] && ((s[1] < s[0] && f[1] < f[0]) || (s[1] > s[0] && f[1] > f[0]))) break;
      if(s[1] == f[1] && ((s[0] < s[1] && f[0] < f[1]) || (s[0] > s[1] && f[0] > f[1]))) break;

      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

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

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 28248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15696 KB Output is correct
2 Correct 60 ms 15696 KB Output is correct
3 Correct 50 ms 15696 KB Output is correct
4 Correct 44 ms 15696 KB Output is correct
5 Correct 46 ms 15952 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 78 ms 31568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -