# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
544506 | model_code | Broken Device 2 (JOI22_device2) | C++17 | 102 ms | 2884 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <utility>
#include <vector>
#include "Anna.h"
namespace {
long long int dp[200];
};
int Declare(void) {
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
for (int i = 4; i <= 140; i++) {
dp[i] = dp[i - 2] + dp[i - 3] + 1;
}
return 140;
}
std::pair<std::vector<int>, std::vector<int> > Anna(long long int A) {
std::vector<int> s, t;
A--;
long long int parity = A % 2;
A /= 2;
A++;
long long int sum = 0;
int len = 0;
while (sum < A) {
sum += dp[++len];
}
long long int k = A - (sum - dp[len]);
std::vector<int> arr;
int index = len;
while (true) {
// A-th in lex order
if (k == 1) {
break;
} else if (k <= dp[index - 2] + 1) {
arr.push_back(2);
k -= 1;
index -= 2;
} else {
arr.push_back(3);
k -= (dp[index - 2] + 1);
index -= 3;
}
}
// std::vector<int> arr;
// for (int i = 0; i < 60; i++) {
// if ((A >> i) & 1LL) {
// arr.push_back(3);
// } else {
// arr.push_back(2);
// }
// }
int b = 1;
s.push_back(b);
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == 3) b ^= 1;
for (int j = 0; j < arr[i]; j++) {
s.push_back(b);
}
}
int sz = s.size();
while (sz < len) {
b ^= 1;
s.push_back(b);
sz++;
}
for (int i = 0; i < s.size(); i++) {
t.push_back(1 - i % 2);
}
if (parity) {
for (int i = 0; i < s.size(); i++) {
s[i] ^= 1;
t[i] ^= 1;
}
}
return std::make_pair(s, t);
}
#include <utility>
#include <vector>
#include "Bruno.h"
namespace {
long long int dp[200];
};
long long int Bruno(std::vector<int> u) {
long long int guess = 0;
long long int len = u.size() / 2;
long long int parity = 0;
if (u[0] == 0) {
parity = 1;
for (int i = 0; i < len * 2; i++) {
u[i] ^= 1;
}
}
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
for (int i = 4; i <= 140; i++) {
dp[i] = dp[i - 2] + dp[i - 3] + 1;
}
/*
* b == 1:
* 1| {11/000}
* |1
* OR
* |1 {11/000}
* 1|
* b == 0:
* |0 {00/111}
* |1
* OR
* 0| {00/111}
* 1|
*/
std::vector<int> arr;
int sum = +1;
int look = 1;
int b = 1;
while (look < len * 2) {
sum += ((u[look] == 1) ? +1 : -1);
if (b == 1) {
if (sum == +3) {
arr.push_back(2);
sum = +1;
b = 1;
} else if (sum == -1) {
arr.push_back(3);
sum = 0;
b = 0;
}
} else {
if (sum == -2) {
arr.push_back(2);
sum = 0;
b = 0;
} else if (sum == +2) {
arr.push_back(3);
sum = +1;
b = 1;
}
}
look++;
}
for (int i = 1; i <= len - 1; i++) {
guess += dp[i];
}
int index = len;
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == 2) {
guess += 1;
index -= 2;
} else {
guess += (dp[index - 2] + 1);
index -= 3;
}
}
guess += 1;
guess--;
guess = (guess * 2) + parity;
guess++;
return guess;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |