Submission #441034

#TimeUsernameProblemLanguageResultExecution timeMemory
441034kig9981Ancient Machine (JOI21_ancient_machine)C++17
60 / 100
78 ms8572 KiB
#include "Anna.h" #include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; #ifdef NON_SUBMIT void Remove(int); void Send(int); #endif void Anna(int N, std::vector<char> S) { vector<int> X, Y, Z; int s=N, e=0, p, mb=7, mbc=1e7; for(int i=0;i<N;i++) { if(S[i]=='X') s=min(s,i); else if(S[i]=='Z') e=i; } if(s>=e) return; for(int i=17;--i>=0;) Send(s&(1<<i) ? 1:0); for(int i=17;--i>=0;) Send(e&(1<<i) ? 1:0); p=s-1; for(int i=s+1;i<e;i++) if(S[i]=='Y' && S[i+1]!='Y') { (S[i+1]=='X' ? X:Z).push_back(Y.size()); Y.push_back(i-p-2); p=i; } for(int t=7;--t;) { int c=0; for(auto y: Y) c+=y<(1<<t)-1; if(mbc>c*t+(N-c)*(t+17)) { mbc=c*t+(N-c)*(t+17); mb=t; } } for(int i=3;--i>=0;) Send(mb&(1<<i) ? 1:0); for(int i=16;--i>=0;) Send(Y.size()&(1<<i) ? 1:0); for(auto y: Y) { if(y<(1<<mb)-1) { for(int i=mb;--i>=0;) Send(y&(1<<i) ? 1:0); } else { for(int i=0;i<mb;i++) Send(1); for(int i=17;--i>=0;) Send(y&(1<<i) ? 1:0); } } p=s-1; for(auto y: Y) Send(S[(p+=y+2)+1]=='Z'); }
#include "Bruno.h" #include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; #ifdef NON_SUBMIT void Remove(int); void Send(int); #endif void Bruno(int N, int L, std::vector<int> A) { int s=0, e=0, j=0, mb=0, p, ysz=0; if(L==0) { for(int i=0;i<N;i++) Remove(i); return; } for(int i=0;i<17;i++) s=2*s+A[j++]; for(int i=0;i<17;i++) e=2*e+A[j++]; for(int i=0;i<3;i++) mb=2*mb+A[j++]; for(int i=0;i<16;i++) ysz=2*ysz+A[j++]; if(ysz==0) { for(int i=0;i<N;i++) Remove(i); return; } vector<char> S(N); vector<int> I, Y; for(int i=0;i<N;i++) S[i]='?'; S[s]='X'; S[e]='Z'; p=s-1; while(ysz--) { int v=0; for(int i=0;i<mb;i++) v=2*v+A[j++]; if(v==(1<<mb)-1) { for(int i=v=0;i<17;i++) v=2*v+A[j++]; } S[p+=v+2]='Y'; Y.push_back(p); } for(auto y: Y) S[y+1]=A[j++] ? 'Z':'X'; for(int i=0;i<N;i++) { if(S[i]=='?') Remove(i); else if(S[i]=='Y') p=i+1; } if(p<e) { Remove(p); S[p]='?'; } for(int i=0;i<N;i++) if(S[i]!='?') { if(S[i]=='Z') { for(;;) { Remove(I.back()); I.pop_back(); if(I.size()==1) { Remove(i); break; } Remove(I.back()); I.pop_back(); } } else I.push_back(i); } while(I.size()) { Remove(I.back()); I.pop_back(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...