| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 63735 | 2018-08-02T15:40:31 Z | bazsi700 | 게임판 (CEOI13_board) | C++14 | 200 ms | 1316 KB |
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
//15:20
bool node1[100005];
bool node2[100005];
bool dist[100005];
bool temp[100005];
bool todeduc[100005];
int lev1,lev2;
int levdist;
void calcdist() {
levdist = 0;
bool rem = false;
for(int i = lev1; i >= 0; i--) {
bool nod1 = node1[i];
bool nod2 = node2[i];
if(rem) {
rem = false;
if(nod2 && !nod1) {
temp[i] = false;
} else if(!nod2 && !nod1) {
temp[i] = true;
rem = true;
} else if(nod1 && nod2) {
temp[i] = true;
rem = true;
} else if(nod1 && !nod2) {
temp[i] = false;
rem = true;
}
} else {
if(nod2 && !nod1) {
temp[i] = true;
} else if(nod1 == nod2) {
temp[i] = false;
} else {
temp[i] = true;
rem = true;
}
}
}
int ind = -1;
for(int i = 0; i <= lev1; i++) {
if(temp[i] && ind == -1) {
ind = 0;
}
if(ind != -1) {
dist[ind++] = temp[i];
}
}
levdist = ind-1;
}
string transf(string s) {
int n = s.length();
string ans = "";
int lev = 0;
bool onleft = true;
int moved = 0;
for(int i = 0; i < n; i++) {
if(s.at(i) == 'R') {
moved++;
} else if(s.at(i) == 'L') {
moved--;
} else {
if(s.at(i) == 'U') {
lev--;
if(onleft && moved == 1) {
ans+= s.at(i);
continue;
}
if(!onleft && moved == -1) {
ans+= s.at(i);
continue;
}
if(moved == 0) {
ans+= s.at(i);
continue;
}
if(moved < 0) {
for(int i = 0; i < -moved; i++) {
ans+= 'L';
}
} else {
for(int i = 0; i < moved; i++) {
ans+= 'R';
}
}
} else {
if(s.at(i) == '1') {
onleft = true;
} else {
onleft = false;
}
lev++;
if(moved == 0) {
ans+= s.at(i);
continue;
}
if(moved < 0) {
for(int i = 0; i < -moved; i++) {
ans+= 'L';
}
} else {
for(int i = 0; i < moved; i++) {
ans+= 'R';
}
}
}
ans+= s.at(i);
moved = 0;
}
}
if(moved < 0) {
for(int i = 0; i < -moved; i++) {
ans+= 'L';
}
} else {
for(int i = 0; i < moved; i++) {
ans+= 'R';
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
string a;
string b;
cin >> a >> b;
a = transf(a);
b = transf(b);
//cout << a << " " << b << endl;
node1[0] = node2[0] = 1;
lev1 = lev2 = 0;
for(int i = 0; i < a.length(); i++) {
if(a.at(i) == '1') {
lev1++;
} else if(a.at(i) == '2') {
lev1++;
node1[lev1] = true;
} else if(a.at(i) == 'L') {
for(int j = lev1; j >= 0; j--) {
if(node1[j]) {
node1[j] = false;
break;
} else {
node1[j] = true;
}
}
} else if(a.at(i) == 'R') {
for(int j = lev1; j >= 0; j--) {
if(!node1[j]) {
node1[j] = true;
break;
} else {
node1[j] = false;
}
}
} else {
node1[lev1] = false;
lev1--;
}
}
for(int i = 0; i < b.length(); i++) {
//cout <<"a" << node2 << " ";
if(b.at(i) == '1') {
lev2++;
} else if(b.at(i) == '2') {
lev2++;
node2[lev2] = true;
} else if(b.at(i) == 'L') {
for(int j = lev2; j >= 0; j--) {
if(node2[j]) {
node2[j] = false;
break;
} else {
node2[j] = true;
}
}
} else if(b.at(i) == 'R') {
for(int j = lev2; j >= 0; j--) {
if(!node2[j]) {
node2[j] = true;
break;
} else {
node2[j] = false;
}
}
} else {
node2[lev2] = false;
lev2--;
}
}
if(lev1 > lev2) {
swap(lev1,lev2);
swap(node1,node2);
} else if(lev1 == lev2) {
bool bad = false;
bool eq = true;
for(int i = 0; i <= lev1; i++) {
if(node1[i] != node2[i]) {
eq = false;
if(node1[i]) {
bad = true;
}
break;
}
}
if(eq) {
cout << 0;
return 0;
}
if(bad) {
swap(node1,node2);
}
}
int wasdif = lev2-lev1;
for(int i = 0; i < lev2-lev1; i++) {
lev2--;
}
ll ans = INF;
ll nod1 = 0;
ll nod2 = 0;
int waslev = lev1;
calcdist();
for(int goesupmore = 0; goesupmore < waslev; goesupmore++) {
if(lev1 <= 25) {
if(nod1 == 0) {
for(int i = 0; i <= lev1; i++) {
nod1*=2;
if(node1[i]) {
nod1++;
}
nod2*=2;
if(node2[i]) {
nod2++;
}
}
}
ans = min(ans,wasdif+goesupmore*2+abs(nod1-nod2));
nod1/=2;
nod2/=2;
} else {
if(levdist <= 30) {
calcdist();
ll dis = 0;
for(int i = 0; i <= levdist; i++) {
dis*=2;
if(dist[i]) {
dis++;
}
}
ans = min(ans,wasdif+goesupmore*2+dis);
if(dis == 0) {
break;
}
lev1--;
lev2--;
} else {
lev1--;
lev2--;
levdist--;
}
}
}
ans = min(ans,wasdif+waslev*2+abs(nod1-nod2));
//cout << node2 << endl;
cout << ans;
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 376 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 7 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 3 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 4 ms | 868 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1038 ms | 1220 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1054 ms | 1236 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 1077 ms | 1316 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |