# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
575576 | Arvin | Ancient Machine (JOI21_ancient_machine) | C++17 | 53 ms | 8864 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 "Anna.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace {
int variable_example = 0;
const int maxN = 1e5 + 5;
}
void Anna(int N, std::vector<char> S) {
// 1 as store this first X or any Z after first Xa
// 0 otherwise
vector<int> v;
ll pos = -1;
bool fX = false;
for(int x=0;x<N;x++){
if(S[x] == 'Z'){
if(fX && (x-1 > pos) && (x+1 == N || S[x+1] != 'Z')){
v.push_back(1);
} else {
v.push_back(0);
}
// Send(fX);
} else if(S[x] == 'Y'){
// Send(0);
v.push_back(0);
} else if(S[x] == 'X'){
if(!fX){
v.push_back(1);
// Send(1);
fX = true;
pos = x;
} else {
v.push_back(0);
// Send(0);
}
}
}
// guaranteed bit 1 at most N/2 + 1
// alternating, only special case where first X and any Z are adjacent.
// first 16 bits are location of first X
// if not exist: ok delete all
// else :
// check first bit after loc
// if 0 length is odd
// - if one:
// - -
// - else:
pos++;
for(int y=0;y<17;y++){
if(pos&(1ll << y)){
Send(1);
} else {
Send(0);
}
}
if(pos == 0){
return;
}
ll cnt[51];
ll sum = 2;
ll table[51];
table[0] = 1; cnt[0] = 1;
table[1] = 1; cnt[1] = 2;
for(int x=2;x<=50;x++){
table[x] = 0;
for(int y=0;y<=x-2;y++){
table[x] += table[y];
}
sum += table[x];
cnt[x] = sum;
}
// cout << "... " << pos << "\n";
while(pos < v.size()){
ll val = 0;
for(int x=49;x>=0;x--){
if(pos+x < v.size() && v[pos+x] == 1){
// cout << "+ " << x << " " << val << "+" << cnt[x] << "\n";
val += cnt[x];
}
}
for(int y=0;y<35;y++){
if(val&(1ll << y)){
Send(1);
} else {
Send(0);
}
}
pos += 50;
}
// Send(v[0]);
// bool skip = false;
// for(int x=0;x<N;x++){
// if(skip){
// skip = false;
// continue;
// }
// if(v[x] == 0){
// if(x+1 == N || v[x+1] == 1){
// Send(0);
// if(x+1 < N && v[x+1] == 1) Send(1);
// else Send(0);
// } else {
// Send(1);
// if(x+2 < N && v[x+2] == 1){
// Send(1);
// } else {
// Send(0);
// }
// skip = true;
// }
// }
// }
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace {
int variable_example = 0;
int FunctionExample(int P) { return 1 - P; }
} // namespace
void Bruno(int N, int L, std::vector<int> A) {
ll pos = 0;
for(int y=0;y<17;y++){
if(A[y] == 1){
pos += (1ll << y);
}
}
if(pos == 0){
for(int y=0;y<N;y++){
Remove(y);
}
return;
}
// for(auto val : A){
// cout << val << " ";
// }cout << "\n";
ll cnt[51];
ll sum = 2;
ll table[51];
table[0] = 1; cnt[0] = 1;
table[1] = 1; cnt[1] = 2;
for(int x=2;x<=50;x++){
table[x] = 0;
for(int y=0;y<=x-2;y++){
table[x] += table[y];
}
sum += table[x];
cnt[x] = sum;
}
vector<int> v(N, 0);
v[pos-1] = 1;
ll idx = 17;
while(idx < L){
ll state = 0;
for(int y=0;y<35;y++){
if(A[idx++] == 1){
state += (1ll << y);
}
}
// cout << "= " << state << "\n";
ll val = 0;
for(int y=49;y>=0;y--){
if(cnt[y] <= state){
// cout << y << " " << state << "-" << cnt[y] << "\n";
state -= cnt[y];
val += (1ll << y);
}
}
for(int y=0;y<50;y++){
if(pos+y >= N) break;
v[pos+y] = ((val&(1ll << y)) != 0);
}
pos += 50;
}
// for(auto val : v){
// cout << val << " ";
// }cout << "\n";
// cout << v.size() << "\n";
vector<int> ans;
pos = -1;
int lst = 0;
for(int x=0;x<v.size();x++){
if(v[x] == 1){
if(pos == -1){
pos = x;
lst = x+1;
} else {
for(int y=x-1;y>=lst;y--){
ans.push_back(y);
}
ans.push_back(x);
lst = x+1;
}
}
}
for(int x=0;x<=pos;x++){
ans.push_back(x);
}
for(int x=lst;x<N;x++){
ans.push_back(x);
}
for(auto val : ans){
// cout << "- " << val << "\n";
Remove(val);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |