oj.uz

Submission #62425

# Submission time Handle Problem Language Result Execution time Memory
62425 2018-07-28T12:42:04 Z Nnandi Board (CEOI13_board) C++14
70 / 100
 200 ms 1008 KB 
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;

string s1, s2;

vector<bool> v1, v2;

void get_exp(string &str, vector<bool> &vb) {
    vb.push_back(true);
    for(char c:str) {
        if(c=='1') {
            vb.push_back(false);
        }
        if(c=='2') {
            vb.push_back(true);
        }
        if(c=='U') {
            vb.resize(vb.size()-1);
        }
        if(c=='R') {
            int it=vb.size()-1;
            while(it >= 0 && vb[it] == true) {
                it--;
            }
            vb[it]=true;
            it++;
            for(;it<vb.size();it++) {
                vb[it] =false;
            }
        }
        if(c=='L') {
            int it=vb.size()-1;
            while(it >= 0 && vb[it] == false) {
                it--;
            }
            vb[it]=false;
            it++;
            for(;it<vb.size();it++) {
                vb[it] =true;
            }
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>s1>>s2;
    get_exp(s1,v1);
    get_exp(s2,v2);
    int dist_min = v1.size() -1 + v2.size() -1;
    bool kell = true;
    int elt = 0;
    for(int i=0;i<min(v1.size(),v2.size()) && kell;i++) {
        elt *= 2;
        if(v2[i] && !v1[i])  {
            elt ++;
        }
        if(!v2[i] && v1[i])  {
            elt --;
        }
        int now_cost = v1.size() + v2.size() - 2*(i+1) + abs(elt);
        if(dist_min > now_cost) {
            dist_min = now_cost;
        }
        if(now_cost > INF) {
            kell = false;
        }
    }
    cout<<dist_min<<endl;
    return 0;
}

Compilation message

board.cpp: In function 'void get_exp(std::__cxx11::string&, std::vector<bool>&)':
board.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;it<vb.size();it++) {
                  ~~^~~~~~~~~~
board.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(;it<vb.size();it++) {
                  ~~^~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:58:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<min(v1.size(),v2.size()) && kell;i++) {
                 ~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 1004 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 1084 ms 1008 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 1081 ms 1008 KB Time limit exceeded
2 Halted 0 ms 0 KB -