oj.uz

Submission #667976

# Submission time Handle Problem Language Result Execution time Memory
667976 2022-12-02T13:03:04 Z 600Mihnea Board (CEOI13_board) C++17
100 / 100
 7 ms 5984 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename T>
void print(vector<T> v)
{
  cout << " ---> ";
  for (auto &x : v)
  {
    cout << x << " ";
  }
  cout << "\n";
}


void add(vector<pair<int, int>> &cur, int x)
{
  if (cur.empty() || cur.back().first != x)
  {
    cur.push_back({x, 1});
  }
  else
  {
    cur.back().second++;
  }
}

void pop(vector<pair<int, int>> &cur)
{
  assert(!cur.empty());
  assert(cur.back().second >= 1);
  cur.back().second--;
  if (cur.back().second == 0)
  {
    cur.pop_back();
  }
}

void inv(vector<pair<int, int>> &cur, int x)
{
  assert(!cur.empty());
  assert(cur.back().second >= 1);
  assert(0 <= x && x <= 1);
  if (cur.back().first == x)
  {
    pop(cur);
    add(cur, 1 - x);
    return;
  }
  assert(cur.back().first == 1 - x);
  pair<int, int> it = cur.back();
  cur.pop_back();
  inv(cur, x);
  it.first = 1 - it.first;
  cur.push_back(it);
}

vector<int> solve_smart(string s)
{
  vector<pair<int, int>> cur;
  for (auto &ch : s)
  {
    if (ch == '1')
    {
      add(cur, 0);
      continue;
    }
    if (ch == '2')
    {
      add(cur, 1);
      continue;
    }
    if (ch == 'U')
    {
      pop(cur);
      continue;
    }
    if (ch == 'R')
    {
      inv(cur, 0);
      continue;
    }
    if (ch == 'L')
    {
      inv(cur, 1);
      continue;
    }
    assert(0);
  }
  vector<int> sol;
  for (auto &it : cur)
  {
    while (it.second > 0)
    {
      it.second--;
      sol.push_back(it.first);
    }
  }
  return sol;
}
vector<int> solve(string s)
{
  vector<int> cur;
  for (auto &ch : s)
  {
    if (ch == '1')
    {
      cur.push_back(0);
      continue;
    }
    if (ch == '2')
    {
      cur.push_back(1);
      continue;
    }
    if (ch == 'U')
    {
      cur.pop_back();
      continue;
    }
    if (ch == 'R')
    {
      int p = (int) cur.size() - 1;
      while (1)
      {
        cur[p] ^= 1;
        if (cur[p] == 1)
        {
          break;
        }
        p--;
        assert(p >= 0);
      }
      continue;
    }

    if (ch == 'L')
    {
      int p = (int) cur.size() - 1;
      while (1)
      {
        cur[p] ^= 1;
        if (cur[p] == 0)
        {
          break;
        }
        p--;
        assert(p >= 0);
      }
      continue;
    }
    assert(0);
  }
  return cur;
}


int get_level(ll x)
{
  if (x == 1)
  {
    return 1;
  }
  else
  {
    assert(x >= 2);
    return 1 + get_level(x / 2);
  }
}

ll solve(ll a, ll b)
{
  if (a == b)
  {
    return 0;
  }
  if (get_level(b) > get_level(a))
  {
    return 1 + solve(a, b / 2);
  }
  if (get_level(a) > get_level(b))
  {
    return 1 + solve(a / 2, b);
  }
  assert(get_level(a) == get_level(b));
  return min(abs(a - b), 2 + solve(a / 2, b / 2));
}

int first_dif = -1;

int get(vector<int>& x, vector<int>& y, ll& dif)
{
  if ((int) x.size() > (int) y.size())
  {
    x.pop_back();

    return 1 + get(x, y, dif);
  }
  if ((int) x.size() < (int) y.size())
  {
    y.pop_back();

    return 1 + get(x, y, dif);
  }
  if (x == y)
  {
    dif = 0;
    return 0;
  }
  assert((int) x.size() == (int) y.size());
  assert((int) x.size() >= 1);
  assert((int) y.size() >= 1);
  int lst_x = x.back(), lst_y = y.back();
  x.pop_back();
  y.pop_back();

  int sol = 2 + get(x, y, dif);

  x.push_back(lst_x);
  y.push_back(lst_y);

  /// dif = what ?

  assert(first_dif != -1);

  int inside = (int) x.size() - first_dif;

  dif *= 2;
  dif += x.back() - y.back();
  if (dif > (ll) 1e18)
  {
    dif = (ll) 1e18;
  }
  if (dif < -(ll) 1e18)
  {
    dif = -(ll) 1e18;
  }
  sol = min((ll) sol, abs(dif));
  return sol;
}


int main()
{
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#endif // ONPC

#ifndef ONPC
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC


  string s, t;
  cin >> s >> t;
  vector<int> x = solve_smart(s), y = solve_smart(t);


  for (int i = 0; i < (int) x.size() && i < (int) y.size(); i++)
  {
    if (x[i] != y[i])
    {
      first_dif = i;
      break;
    }
  }
  ll dif;
  int sol = get(x, y, dif);
  cout << sol << "\n";
  return 0;
}
/**
**/

Compilation message

board.cpp: In function 'int get(std::vector<int>&, std::vector<int>&, ll&)':
board.cpp:229:7: warning: unused variable 'inside' [-Wunused-variable]
  229 |   int inside = (int) x.size() - first_dif;
      |       ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 824 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5296 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5344 KB Output is correct
2 Correct 6 ms 5540 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 4 ms 1360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5376 KB Output is correct
2 Correct 7 ms 5600 KB Output is correct
3 Correct 3 ms 1204 KB Output is correct
4 Correct 2 ms 1620 KB Output is correct
5 Correct 2 ms 1620 KB Output is correct
6 Correct 7 ms 5984 KB Output is correct