| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25622 |
2017-06-23T08:40:53 Z |
Extazy |
Board (CEOI13_board) |
C++14 |
|
200 ms |
2944 KB |
#include <bits/stdc++.h>
#define string vector < int >
using namespace std;
const int N = 1<<17;
const int BASE = 1000;
const int BASE_LENGTH = 3;
const vector < int > V0 = { 0 };
const vector < int > V1 = { 1 };
const vector < int > V2 = { 2 };
string add(string a, string b) {
string c,d;
int p=0,t,i;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
while(a.size()<b.size()) a.push_back(0);
while(a.size()>b.size()) b.push_back(0);
for(i=0;i<(int)(a.size());i++) {
t=p+a[i]+b[i];
p=t/BASE;
t%=BASE;
c.push_back(t);
}
if(p>0) c.push_back(p);
reverse(c.begin(),c.end());
for(i=0;i<(int)(c.size());i++) if(c[i]!=0) break;
for(;i<(int)(c.size());i++) d.push_back(c[i]);
if(d.empty()) d.push_back(0);
return d;
}
bool cmp(string a, string b) {
if(a.size()<b.size()) return true;
if(a.size()>b.size()) return false;
for(int i=0;i<(int)(a.size());i++) {
if(a[i]<b[i]) return true;
if(a[i]>b[i]) return false;
}
return false;
}
string get_min(string a, string b) {
return ((cmp(a,b)==true) ? a : b);
}
string get_max(string a, string b) {
return ((cmp(a,b)==true) ? b : a);
}
string subtract(string a, string b) {
string c,d;
int i,j;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
while(a.size()>b.size()) b.push_back(0);
for(i=0;i<(int)(a.size());i++) {
if(a[i]>=b[i]) {
c.push_back(a[i]-b[i]);
continue;
}
for(j=i+1;j<(int)(a.size());j++) {
if(a[j]>0) {
--a[j];
break;
}
else {
a[j]=BASE-1;
}
}
c.push_back(a[i]+BASE-b[i]);
}
reverse(c.begin(),c.end());
for(i=0;i<(int)(c.size());i++) if(c[i]!=0) break;
for(;i<(int)(c.size());i++) d.push_back(c[i]);
if(d.empty()) d.push_back(0);
return d;
}
string div2(string a) {
int i,p=0;
string b,c;
for(i=0;i<(int)(a.size());i++) {
p*=BASE;
p+=a[i];
b.push_back(p/2);
p%=2;
}
for(i=0;i<(int)(b.size());i++) if(b[i]!=0) break;
for(;i<(int)(b.size());i++) c.push_back(b[i]);
if(c.empty()) c.push_back(0);
return c;
}
struct node {
int level;
string number;
node() {
level=0;
number=V1;
}
void move(char a) {
if(a=='1') {
++level;
number=add(number,number);
}
else if(a=='2') {
++level;
number=add(add(number,number),V1);
}
else if(a=='L') {
number=subtract(number,V1);
}
else if(a=='R') {
number=add(number,V1);
}
else { //a=='U'
--level;
number=div2(number);
}
}
};
char a[N],b[N];
int digcnt[N];
int n,m;
node node1,node2;
string ans,curr;
void print(vector < int > a) {
printf("%d", a[0]);
for(int i=1;i<(int)(a.size());i++) {
int j=BASE_LENGTH-digcnt[a[i]];
while(j--) printf("0");
printf("%d", a[i]);
}
printf("\n");
}
int main() {
int i;
for(i=0;i<10;i++) digcnt[i]=1;
for(i=10;i<N;i++) digcnt[i]=digcnt[i/10]+1;
scanf("%s", a+1);
n=strlen(a+1);
scanf("%s", b+1);
m=strlen(b+1);
for(i=1;i<=n;i++) {
node1.move(a[i]);
}
for(i=1;i<=m;i++) {
node2.move(b[i]);
}
//ans=node1.level+node2.level;
//if(node1.level>=1 && node2.level>=1) ans=min(ans,node1.level+node2.level-1ll);
curr=V0;
while(node1.level!=node2.level) {
if(node1.level>node2.level) curr=add(curr,V1),node1.move('U');
else curr=add(curr,V1),node2.move('U');
}
ans=add(curr,subtract(get_max(node1.number,node2.number),get_min(node1.number,node2.number)));
while(node1.level>0) {
curr=add(curr,V2);
node1.move('U');
node2.move('U');
ans=get_min(ans,add(curr,subtract(get_max(node1.number,node2.number),get_min(node1.number,node2.number))));
}
print(ans);
return 0;
}
Compilation message
board.cpp: In function 'int main()':
board.cpp:160:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", a+1);
^
board.cpp:162:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", b+1);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
33 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
163 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
63 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
43 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
2808 KB |
Output is correct |
| 2 |
Execution timed out |
200 ms |
2808 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
200 ms |
2944 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
200 ms |
2944 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
200 ms |
2944 KB |
Execution timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
