oj.uz

Submission #441042

# Submission time Handle Problem Language Result Execution time Memory
441042 2021-07-04T01:02:13 Z kig9981 Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 11 ms 2024 KB 
#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, 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]=='X') {
		X.push_back(i-p-2);
		p=i;
	}
	p=s-1;
	for(int i=s+1;i<e;i++) if(S[i]=='Y' && S[i+1]=='Z') {
		Z.push_back(i-p-2);
		p=i;
	}
	for(int t=7;--t;) {
		int c=0;
		for(auto y: X) 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(X.size()&(1<<i) ? 1:0);
	for(auto y: X) {
		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);
		}
	}
	mb=7; mbc=1e7;
	for(int t=7;--t;) {
		int c=0;
		for(auto y: Z) 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(Z.size()&(1<<i) ? 1:0);
	for(auto y: Z) {
		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);
		}
	}
}
#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, tot=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++];
	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;
	for(int i=0;i<3;i++) mb=2*mb+A[j++];
	for(int i=0;i<16;i++) ysz=2*ysz+A[j++];
	tot+=ysz;
	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';
		S[p+1]='X';
		Y.push_back(p);
	}
	for(int i=mb=0;i<3;i++) mb=2*mb+A[j++];
	for(int i=ysz=0;i<16;i++) ysz=2*ysz+A[j++];
	tot+=ysz;
	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';
		S[p+1]='Z';
		Y.push_back(p);
	}
	if(ysz==0) {
		for(int i=0;i<N;i++) Remove(i);
		return;
	}
	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();
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 484 KB Output is correct
2 Correct 0 ms 484 KB Output is correct
3 Correct 0 ms 496 KB Output is correct
4 Runtime error 1 ms 612 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2024 KB Wrong Answer [2]
2 Halted 0 ms 0 KB -