oj.uz

Submission #782878

# Submission time Handle Problem Language Result Execution time Memory
782878 2023-07-14T10:44:14 Z RecursiveCo Board (CEOI13_board) C++14
70 / 100
 200 ms 1044 KB 
// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long

vector<int> compress(string s) {
    stack<int> tobepush;
    stack<int> sst;
    int n = s.size();
    forto(n, i) {
        switch (s[i]) {
            case 'U':
                sst.pop();
                break;
            case '1':
                sst.push(1);
                break;
            case '2':
                sst.push(2);
                break;
            case 'L':
                while (1) {
                    int op = sst.top();
                    sst.pop();
                    tobepush.push(op == 1? 2: 1);
                    if (op == 2) break;
                }
                while (!tobepush.empty()) {
                    sst.push(tobepush.top());
                    tobepush.pop();
                }
                break;
            case 'R':
                while (1) {
                    int op = sst.top();
                    sst.pop();
                    tobepush.push(op == 1? 2: 1);
                    if (op == 1) break;
                }
                while (!tobepush.empty()) {
                    sst.push(tobepush.top());
                    tobepush.pop();
                }
                break;
        }
    }
    vector<int> res;
    while (!sst.empty()) res.push_back(sst.top()), sst.pop();
    rev(res);
    return res;
}

signed main() {
    improvePerformance;
    //getTest;

    //eachTest {
        string s, t;
        cin >> s;
        cin >> t;
        vector<int> S = compress(s);
        vector<int> T = compress(t);
        if (S > T) swap(S, T);
        int slev = S.size();
        int tlev = T.size();
        vector<int> moves;
        int cnt = 0;
        forto(min(slev, tlev), i) {
            if (S[i] == T[i]) cnt *= 2;
            else if (S[i] == 1) cnt = cnt * 2 + 1;
            else cnt = cnt * 2 - 1;
            if (cnt > 250000) break;
            moves.push_back(cnt);
        }
        int ans = slev + tlev;
        forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
        out(ans);
    //}
}

Compilation message

board.cpp: In function 'std::vector<long long int> compress(std::string)':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:24:5: note: in expansion of macro 'forto'
   24 |     forto(n, i) {
      |     ^~~~~
board.cpp: In function 'int main()':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:82:9: note: in expansion of macro 'forto'
   82 |         forto(min(slev, tlev), i) {
      |         ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
board.cpp:90:9: note: in expansion of macro 'forto'
   90 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~
board.cpp:15:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                              ~~~~~~^~~~~~~~
board.cpp:90:9: note: in expansion of macro 'forto'
   90 |         forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
      |         ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 316 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 1044 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 1072 ms 920 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 1060 ms 912 KB Time limit exceeded
2 Halted 0 ms 0 KB -