Submission #61859

#	Time	Username	Problem	Language	Result	Execution time	Memory
61859		Benq	Board (CEOI13_board)	C++11	0 / 100	9 ms	3480 KiB

board

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int fdiv(int x) {
    if (x % 2 == 0) return x/2;
    if (x > 0) return x/2;
    return x/2-1;
}

string compress(string x) {
    vi cur;
    for (char c: x) 
        switch(c) {
            case '1':
                cur.pb(0);
                break;
            case '2':
                cur.pb(1);
                break;
            case 'U':
                cur[sz(cur)-2] += fdiv(cur.back());
                cur.pop_back();
            case 'L':
                cur.back() --;
            case 'R':
                cur.back() ++;
        }
    FORd(i,1,sz(cur)) {
        int t = fdiv(cur[i]);
        cur[i-1] += t;
        cur[i] -= 2*t;
    }
    string res;
    for (int i: cur) res += char('0'+i);
    return res;
}

ll dif[MX];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string x; cin >> x; x = compress(x);
    string y; cin >> y; y = compress(y);
    int ad = 0;
    ll ans = INF;
    while (sz(y) > sz(x)) y.pop_back(), ad ++;
    while (sz(x) > sz(y)) x.pop_back(), ad ++;
    
    if (x > y) swap(x,y);
    dif[0] = 0;
    F0R(i,min(sz(x),sz(y))) {
        dif[i+1] = 2*dif[i];
        if (x[i] != y[i]) {
            if (x[i] == '0') dif[i+1] ++;
            else dif[i+1] --;
        }
        dif[i+1] = min(dif[i+1],INF);
    }
    F0R(i,sz(x)+1) ans = min(ans,ad+2*(sz(x)-i)+dif[i]);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10