oj.uz

Submission #440936

# Submission time Handle Problem Language Result Execution time Memory
440936 2021-07-03T13:52:11 Z kig9981 Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 114 ms 9932 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, 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);
	Send(X.size()>Z.size());
	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);
		}
	}
	if(X.size()>Z.size()) swap(X,Z);
	if(X.empty()) {
		Send(0); Send(0); Send(0);
		return;
	}
	for(int i=X.size();--i;) X[i]-=X[i-1]+1;
	mb=7; mbc=1e7;
	for(int t=7;--t;) {
		int c=0;
		for(auto x: X) c+=x<(1<<t)-1;
		if(mbc>c*t+(N-c)*(t+15)) {
			mbc=c*t+(N-c)*(t+15);
			mb=t;
		}
	}
	for(int i=3;--i>=0;) Send(mb&(1<<i) ? 1:0);
	for(auto x: X) {
		if(x<(1<<mb)-1) {
			for(int i=mb;--i>=0;) Send(x&(1<<i) ? 1:0);
		}
		else {
			for(int i=0;i<mb;i++) Send(1);
			for(int i=15;--i>=0;) Send(x&(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;
	char ch;
	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++];
	ch=A[j++] ? 'Z':'X';
	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);
	}
	p=-1; mb=0;
	for(int i=0;i<3;i++) mb=2*mb+A[j++];
	while(j<L) {
		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<15;i++) v=2*v+A[j++];
		}
		S[Y[p+=v+1]+1]=ch;
	}
	ch=(int)'X'+'Z'-ch;
	for(auto y: Y) if(S[y+1]=='?') S[y+1]=ch;
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 484 KB Output is correct
2 Correct 1 ms 488 KB Output is correct
3 Correct 1 ms 576 KB Output is correct
4 Correct 1 ms 568 KB Output is correct
5 Correct 1 ms 564 KB Output is correct
6 Correct 1 ms 576 KB Output is correct
7 Correct 1 ms 484 KB Output is correct
8 Correct 1 ms 580 KB Output is correct
9 Correct 1 ms 576 KB Output is correct
10 Correct 0 ms 496 KB Output is correct
11 Correct 1 ms 488 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 92 ms 9260 KB Partially correct
2 Partially correct 95 ms 9644 KB Partially correct
3 Partially correct 114 ms 9932 KB Partially correct
4 Partially correct 102 ms 9660 KB Partially correct
5 Partially correct 111 ms 9776 KB Partially correct
6 Partially correct 114 ms 9676 KB Partially correct
7 Partially correct 92 ms 9652 KB Partially correct
8 Partially correct 88 ms 9660 KB Partially correct
9 Partially correct 99 ms 9680 KB Partially correct
10 Partially correct 110 ms 9716 KB Partially correct
11 Partially correct 95 ms 9672 KB Partially correct
12 Partially correct 106 ms 9748 KB Partially correct
13 Correct 72 ms 8136 KB Output is correct
14 Correct 65 ms 7952 KB Output is correct
15 Correct 65 ms 8212 KB Output is correct
16 Correct 60 ms 8248 KB Output is correct
17 Correct 56 ms 6744 KB Output is correct
18 Correct 60 ms 6648 KB Output is correct
19 Correct 71 ms 6668 KB Output is correct
20 Partially correct 82 ms 9612 KB Partially correct
21 Partially correct 75 ms 9604 KB Partially correct
22 Correct 52 ms 6840 KB Output is correct
23 Incorrect 13 ms 2564 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -