oj.uz

Submission #257050

# Submission time Handle Problem Language Result Execution time Memory
257050 2020-08-03T14:56:29 Z doowey Board (CEOI13_board) C++14
40 / 100
 200 ms 2940 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<int> res = {1};
    for(char x : t){
        if(x == '1') res.push_back(0);
        else if(x == '2') res.push_back(1);
        else if(x == 'U'){
            res.pop_back();
        }
        else if(x == 'L'){
            int id = res.size() - 1;
            while(id >= 0){
                if(res[id] == 0){
                    res[id] ^= 1;
                }
                else{
                    res[id] ^= 1;
                    break;
                }
                id -- ;
            }
        }
        else{
            int id = res.size() - 1;
            while(id >= 0){
                if(res[id] == 0){
                    res[id] ^= 1;
                    break;
                }
                else{
                    res[id] ^= 1;
                }
                id -- ;
            }
        }
    }
    return res;
}

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

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

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Incorrect 1 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Incorrect 1 ms 1920 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2048 KB Output is correct
2 Correct 4 ms 2176 KB Output is correct
3 Correct 3 ms 2176 KB Output is correct
4 Incorrect 1 ms 1920 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 2848 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 2940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 2700 KB Time limit exceeded
2 Halted 0 ms 0 KB -