oj.uz

Submission #61860

# Submission time Handle Problem Language Result Execution time Memory
61860 2018-07-27T00:51:30 Z Benq Board (CEOI13_board) C++11
100 / 100
 8 ms 3664 KB 
#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();
                break;
            case 'L':
                cur.back() --;
                break;
            case 'R':
                cur.back() ++;
                break;
        }
    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
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 720 KB Output is correct
2 Correct 3 ms 720 KB Output is correct
3 Correct 4 ms 936 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 936 KB Output is correct
2 Correct 8 ms 1252 KB Output is correct
3 Correct 6 ms 1392 KB Output is correct
4 Correct 3 ms 1392 KB Output is correct
5 Correct 3 ms 1392 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1392 KB Output is correct
2 Correct 6 ms 1588 KB Output is correct
3 Correct 6 ms 1644 KB Output is correct
4 Correct 3 ms 1644 KB Output is correct
5 Correct 3 ms 1644 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2620 KB Output is correct
2 Correct 7 ms 2620 KB Output is correct
3 Correct 3 ms 2620 KB Output is correct
4 Correct 4 ms 2620 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2620 KB Output is correct
2 Correct 6 ms 2804 KB Output is correct
3 Correct 3 ms 2804 KB Output is correct
4 Correct 3 ms 2804 KB Output is correct
5 Correct 6 ms 3268 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3268 KB Output is correct
2 Correct 7 ms 3268 KB Output is correct
3 Correct 6 ms 3424 KB Output is correct
4 Correct 3 ms 3424 KB Output is correct
5 Correct 3 ms 3424 KB Output is correct
6 Correct 7 ms 3664 KB Output is correct