# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
524660 | amunduzbaev | Ancient Machine (JOI21_ancient_machine) | C++17 | 57 ms | 8328 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 __int128
const int B = 93;
const ll one = (ll)1;
const ll b = 65;
ll dp[B][2];
void Anna(int n, vector<char> s) {
int f = -1;
for(int i=0;i<n;i++){
if(s[i] == 'X') { f = i; break; }
}
int C = (n + B - 1) / B;
if(f == -1){
return;
}
for(int i=0;i<17;i++) Send(f >> i & 1);
vector<int> res(n);
//~ res[f] = 1;
for(int i=f+1;i<n;i++){
if(s[i] == 'Z'){
res[i] = 1;
if(s[i-1] == 'Z') res[i-1] = 0;
}
}
dp[0][0] = dp[0][1] = 1;
for(int i=1;i<B;i++){
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
//~ auto get = [&](vector<int> x) {
//~ ii res = (ii)0;
//~ for(int i=0;i<(int)x.size();i++){
//~ if(x[i]) res += dp[i][0];
//~ } return res;
//~ };
//~ for(int i=0;i<n;i++) cout<<res[i]<<" ";
//~ cout<<"\n";
vector<int> rr;
for(int i=0;i<C;i++){
vector<int> tmp = vector<int>(res.begin() + i * B, res.begin() + min(n, (i + 1) * B));
ll v = 0;
for(int i=0;i<(int)tmp.size();i++){
if(tmp[i]) v = v + dp[i][0];
}
for(int j=0;j<b;j++){
Send(v >> j & 1);
}
}
}
#include "Bruno.h"
#include "bits/stdc++.h"
using namespace std;
#define ll __int128
const int B = 93;
const ll one = (ll)1;
const ll b = 65;
void Bruno(int n, int l, vector<int> a) {
ll dp[B][2] {};
dp[0][0] = dp[0][1] = 1;
for(int i=1;i<B;i++){
dp[i][0] = dp[i-1][0] + dp[i-1][1];
dp[i][1] = dp[i-1][0];
}
if(!l){
for(int i=0;i<n;i++) Remove(i);
return;
}
int f = 0;
for(int i=0;i<17;i++) f |= (a[i] << i);
a.erase(a.begin(), a.begin() + 17);
//~ cout<<f<<endl;
int C = (n + B - 1) / B;
vector<int> is(C * B);
for(int i=0;i<C;i++){
ll v = 0;
for(int j=i*b;j<(i+1)*b;j++){
v |= ((a[j] * one) << (j - i*b));
}
for(int l=B-1;~l;l--){
if(v >= dp[l][0]) is[i * B + l] = 1, v -= dp[l][0];
}
//~ cout<<"here"<<endl;
}
for(int i=0;i<f;i++) Remove(i);
int last = f; //, f = -1;
for(int i=f+1;i<n;i++){
if(is[i]){
int j = i - 1;
while(j > last) Remove(j--);
Remove(i); last = i;
}
}
int j = n - 1;
while(j > last) Remove(j--);
Remove(f);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |