oj.uz

Submission #117194

# Submission time Handle Problem Language Result Execution time Memory
117194 2019-06-15T09:33:18 Z JohnTitor Board (CEOI13_board) C++11
100 / 100
 10 ms 1032 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
using ll=long long;
using ld=long double;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "Board"
class number{
protected:
    vector <pair <int, int>> v;
    void append_zero(int sz=1){
        if(sz==0) return;
        if(v.back().first==0) v.back().second++;
        else v.pb(mp(0, sz));
    }
    void append_one(int sz=1){
        if(sz==0) return;
        if(v.back().first==1) v.back().second++;
        else v.pb(mp(1, sz));
    }
    void truncate(){
        v.back().second--;
        if(v.back().second==0) v.pop_back();
    }
    void take_one(){
        int added_one=0;
        if(v.back().first==0){
            added_one+=v.back().second;
            v.pop_back();
        }
        v.back().second--;
        if(v.back().second==0) v.pop_back();
        append_zero();
        append_one(added_one);
    }
    void add_one(){
        int added_zero=0;
        if(v.back().first==1){
            added_zero+=v.back().second;
            v.pop_back();
        }
        v.back().second--;
        if(v.back().second==0) v.pop_back();
        append_one();
        append_zero(added_zero);
    }
public:
    number(){
        v.clear();
        v.pb(mp(0, 1));
    }
    void left_child(){
        append_zero();
    }
    void right_child(){
        append_one();
    }
    void parent(){
        truncate();
    }
    void left_cousin(){
        take_one();
    }
    void right_cousin(){
        add_one();
    }
    void process_token(char c){
        if(c=='1') left_child();
        else if(c=='2') right_child();
        else if(c=='U') parent();
        else if(c=='L') left_cousin();
        else right_cousin();
    }
    void input(){
        string s;
        cin>>s;
        for(auto c: s) process_token(c);
    }
    deque <int> get_uncompresed_form(){
        deque <int> res;
        for(auto x: v) FFOR(j, 0, x.second) res.pb(x.first);
        return res;
    }
} A, B;
deque <int> x, y;
int main(){
    #ifdef Uiharu
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Uiharu
    A.input();
    B.input();
    x=A.get_uncompresed_form();
    y=B.get_uncompresed_form();
    while((!x.empty())&&(!y.empty())&&(x.front()==y.front())){
        x.pop_front();
        y.pop_front();
    }
    int ans=x.size()+y.size();
    int px=0, py=0;
    FFOR(i, 0, min(x.size(), y.size())){
        px=px*2+x[i];
        py=py*2+y[i];
        if(abs(px-py)>=ans) break;
        ans=min(ans, (int)(abs(px-py)+x.size()-i-1+y.size()-i-1));
    }
    writeln(ans);
}

Compilation message

board.cpp: In function 'int main()':
board.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
board.cpp:136:5: note: in expansion of macro 'FFOR'
     FFOR(i, 0, min(x.size(), y.size())){
     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 8 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 428 KB Output is correct
2 Correct 9 ms 768 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 872 KB Output is correct
2 Correct 10 ms 872 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 888 KB Output is correct
2 Correct 9 ms 1012 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 10 ms 960 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 876 KB Output is correct
2 Correct 9 ms 1032 KB Output is correct
3 Correct 9 ms 816 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 9 ms 960 KB Output is correct