oj.uz

Submission #52818

# Submission time Handle Problem Language Result Execution time Memory
52818 2018-06-27T01:08:51 Z updown1 Board (CEOI13_board) C++17
100 / 100
 6 ms 3444 KB 
/*
structure looks like:
  _
 / \
/   \
and answer can't be more than slightly more than 200,000 (I'm using 300,000). Calculate from top to bottom
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, at1)
#define ffj For(j, 0, at2)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
const int MAXN=100001, INF=1000000000000000000;
///500,000,000
string str1, str2;
int loc1[MAXN], loc2[MAXN], at1, at2, curr, out = INF, rig;

void fix1(int i) {
    if (loc1[i] > 1) {
        loc1[i-1] += loc1[i]/2;
        loc1[i] %= 2;
    }
    if (loc1[i] < 0) {
        loc1[i-1] += (loc1[i]-1)/2;
        loc1[i] = (loc1[i]+INF)%2;
    }
}
void fix2(int i) {
    if (loc2[i] > 1) {
        loc2[i-1] += loc2[i]/2;
        loc2[i] %= 2;
    }
    if (loc2[i] < 0) {
        loc2[i-1] += (loc2[i]-1)/2;
        loc2[i] = (loc2[i]+INF)%2;
    }
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> str1 >> str2;
    loc1[0] = loc2[0] = 1;
    for (char i: str1) {
        if (i == '1') {at1++; loc1[at1] = 0;}
        if (i == '2') {at1++; loc1[at1] = 1;}
        if (i == 'L') {loc1[at1]--;}
        if (i == 'R') {loc1[at1]++;}
        if (i == 'U') {fix1(at1); at1--;}
    }
    for (int i=at1; i>=1; i--) fix1(i);
    assert(loc1[0] == 1);
    at1++;
    //ffi w<< loc1[i]; w<<e;
    for (char i: str2) {
        if (i == '1') {at2++; loc2[at2] = 0;}
        if (i == '2') {at2++; loc2[at2] = 1;}
        if (i == 'L') {loc2[at2]--;}
        if (i == 'R') {loc2[at2]++;}
        if (i == 'U') {fix2(at2); at2--;}
    }
    for (int i=at2; i>=1; i--) fix2(i);
    assert(loc1[0] == 1);
    at2++;
    //ffj w<< loc2[j]; w<<e;
    For (i, 0, min(at1, at2)) {
        if (rig == 0 && loc1[i] != loc2[i]) {
            if (loc1[i] < loc2[i]) rig = 2;
            else rig = 1;
        }
        curr *= 2;
        if (rig == 1) curr += loc1[i] - loc2[i];
        if (rig == 2) curr += loc2[i] - loc1[i];
        out = min(out, curr + at1 - i - 1 + at2 - i - 1);
        if (curr > out) break;
    }
    w<< out<<e;
}

Compilation message

board.cpp:49:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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