oj.uz

답안 #257117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257117 2020-08-03T15:45:12 Z doowey 게임판 (CEOI13_board) C++14
100 / 100
 4 ms 1420 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

vector<int> gen(string t){
    vector<pii> cc = {mp(1,1)}; // {len, bit}
    for(char x : t){
        if(x == '1') {
            if(cc.back().se == 0) cc.back().fi ++ ;
            else cc.push_back(mp(1, 0));
        }
        else if(x == '2') {
            if(cc.back().se == 1) cc.back().fi ++ ;
            else cc.push_back(mp(1, 1));
        }
        else if(x == 'U'){
            cc.back().fi -- ;
            if(cc.back().fi == 0)
                cc.pop_back();
        }
        else if(x == 'L'){

            int las;
            if(cc.back().se == 0){
                las = cc.back().fi;
                cc.pop_back();
                if(cc.back().fi == 1){
                    cc.pop_back();
                    cc.back().fi ++ ;
                }
                else{
                    cc.back().fi -- ;
                    cc.push_back(mp(1, 0));
                }
                cc.push_back(mp(las, 1));
            }
            else{
                if(cc.back().fi == 1){
                    cc.pop_back();
                    cc.back().fi ++ ;
                }
                else{
                    cc.back().fi -- ;
                    cc.push_back(mp(1, 0));
                }
            }
        }
        else{
            int las;
            if(cc.back().se == 1){
                las = cc.back().fi;
                cc.pop_back();
                if(cc.back().fi == 1){
                    cc.pop_back();
                    cc.back().fi ++ ;
                }
                else{
                    cc.back().fi -- ;
                    cc.push_back(mp(1, 1));
                }
                cc.push_back(mp(las, 0));
            }
            else{
                if(cc.back().fi == 1){
                    cc.pop_back();
                    cc.back().fi ++ ;
                }
                else{
                    cc.back().fi -- ;
                    cc.push_back(mp(1, 1));
                }
            }

        }
    }
    vector<int> res;
    for(auto x : cc){
        for(int y = 0; y < x.fi; y ++ ){
            res.push_back(x.se);
        }
    }
    return res;
}

const ll MX = (int)1e9 + 7;
const int N = (int)2e5 + 10;

int main(){
    fastIO;
    string a, b;
    cin >> a >> b;
    vector<int> p = gen(a);
    vector<int> q = gen(b);
    if(p.size() > q.size())
        swap(p,q);
    ll low = (int)p.size() - 1 + (int)q.size() - 1;
    ll dif = 0;
    int side = -1;
    for(int com = 0; com < min(p.size(), q.size()); com ++ ){
        dif *= 2ll;
        if(dif >= MX) break;
        if(p[com] != q[com]){
            if(side == -1){
                if(p[com] == 1) side = 0;
                else side = 1;
            }
            if(p[com] == 1){
                if(side == 0) dif ++ ;
                else dif -- ;
            }
            else{
                if(side == 1) dif ++ ;
                else dif -- ;
            }
        }
        low = min(low, dif + (ll)p.size() - (com + 1) + (ll)q.size() - (com + 1));
    }
    cout << low << "\n";
    return 0;
}

Compilation message

board.cpp: In function 'int main()':
board.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int com = 0; com < min(p.size(), q.size()); com ++ ){
                      ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1404 KB Output is correct
2 Correct 4 ms 1404 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 1 ms 580 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1404 KB Output is correct
2 Correct 3 ms 1420 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 3 ms 1420 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1404 KB Output is correct
2 Correct 4 ms 1420 KB Output is correct
3 Correct 2 ms 1276 KB Output is correct
4 Correct 1 ms 536 KB Output is correct
5 Correct 1 ms 536 KB Output is correct
6 Correct 3 ms 1420 KB Output is correct