Submission #126888

#TimeUsernameProblemLanguageResultExecution timeMemory
126888eriksuenderhaufBoard (CEOI13_board)C++11
100 / 100
104 ms732 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; ll bitx[MAXN / 62 + 1], bity[MAXN / 62 + 1]; char str[MAXN]; int process(ll *bit) { bit[0] = 2305843009213693952ll; scanf("%s", str); int n = strlen(str); int ret = 1; for (int i = 0; i < n; i++) { if (str[i] == '1') // add a 0 to the end bit[ret / 62] &= 4611686018427387903ll ^ (1ll << (61 - (ret % 62))); if (str[i] == '2') // add a 1 to the end bit[ret / 62] |= (1ll << (61 - (ret % 62))); if (str[i] == '1' || str[i] == '2') ret++; if (str[i] == 'L') { // go left ret--; bit[ret / 62] -= (1ll << (61 - (ret % 62))); for (int i = ret / 62; bit[i] < 0; i--) { bit[i] += 4611686018427387904ll; bit[i-1]--; } ret++; } if (str[i] == 'R') { // go right ret--; bit[ret / 62] += (1ll << (61 - (ret % 62))); for (int i = ret / 62; bit[i] > 4611686018427387903ll; i--) { bit[i] -= 4611686018427387904ll; bit[i-1]++; } ret++; } if (str[i] == 'U') ret--; } return ret; } int main() { int n = process(bitx); int m = process(bity); int cur = 0, ans = INF; for (int i = 0; i < min(n, m) && abs(cur) <= ans; i++) { cur = 2 * cur + ((bitx[i / 62] >> (61 - (i % 62))) & 1) - ((bity[i / 62] >> (61 - (i % 62))) & 1); ans = min(ans, abs(cur) + n + m - 2 * (i+1)); } pri(ans); return 0; }

Compilation message (stderr)

board.cpp: In function 'int process(ll*)':
board.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str);
  ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...