Submission #386418

#	Time	Username	Problem	Language	Result	Execution time	Memory
386418		haojiandan	Ancient Machine (JOI21_ancient_machine)	C++17	40 / 100	118 ms	12120 KiB

Anna

#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;


void Anna(int n,vector<char> s) {
	int a;
	for (int i=0;i<n;i+=5) {
		a=0;
		for (int j=i;j<=i+4;j++) {
			a=a*3+(j<n?s[j]-'X':0);
		}
		for (int j=0;j<=7;j++) Send(a>>j&1);
	}
}

Bruno

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
const int maxn=(1e5)+10;
int N,s[maxn];
int b[maxn],tot;
int pre[maxn],nxt[maxn];
queue<int> q;
int zuo[maxn],you[maxn];
int alive[maxn];
int NXT[maxn],PRE[maxn],ok[maxn];
void del(int x) {
	//printf("del %d\n",x);
	Remove(x); alive[x]=0;
	if (nxt[x]<N) pre[nxt[x]]=pre[x];
	if (pre[x]!=-1) nxt[pre[x]]=nxt[x];
	
	if (s[x]==1) {
		if (NXT[x]<N) {
			PRE[NXT[x]]=PRE[x];
		}
		if (PRE[x]!=-1) NXT[PRE[x]]=NXT[x];
	}
}
}  // namespace

void Bruno(int n,int len,vector<int> A) {
	int a,now=0; N=n;
	for (int i=0;i<n;i+=5) {
		a=0;
		for (int j=0;j<=7;j++) {
			if (A[now]) a+=(1<<j);
			now++;
		}
		for (int j=i+4;j>=i;j--) {
			if (j<n) {
				s[j]=a%3;
			}
			a/=3;
		}
	}
	//for (int i=0;i<n;i++) printf("%d ",s[i]); puts("");
	int mn=-1,mx=-1;
	for (int i=0;i<n;i++)
		if (s[i]==0) { mn=i; break; }
	for (int i=n-1;i>=0;i--)
		if (s[i]==2) { mx=i; break; }
	if (mn==-1||mx==-1||mn>mx) {
		for (int i=0;i<n;i++) Remove(i);
		return;
	}
	
	tot=0;
	b[++tot]=-1;
	for (int i=0;i<n;i++) {
		ok[i]=0; alive[i]=1;
		if (s[i]==1) b[++tot]=i;
	}
	b[++tot]=n;
	
	for (int i=0;i<n;i++) pre[i]=i-1,nxt[i]=i+1;
	
	for (int i=0;i<mn;i++) del(i);
	for (int i=mx+1;i<n;i++) del(i);
	for (int i=mn+1;i<mx;i++) if (s[i]==1&&s[i+1]==1) del(i+1);
	
	now=-1;
	for (int i=mn+1;i<mx;i++) if (s[i]==1&&alive[i]) {
		PRE[i]=now;
		now=i;
	}
	now=n+1;
	for (int i=mx-1;i>mn;i--) if (s[i]==1&&alive[i]) {
		NXT[i]=now;
		now=i;
	}
	
	for (int i=mn;i<=mx;i++) {
		if (s[i]==0) now=i;
		if (s[i]==1) zuo[i]=now;
	}
	for (int i=mx;i>=mn;i--) {
		if (s[i]==2) now=i;
		if (s[i]==1) you[i]=now;
	}
//	printf("%d\n",NXT[1]);
	q=queue<int>();
	for (int i=mn;i<=mx;i++) if (s[i]==1&&alive[i]) {
		if (zuo[i]>PRE[i]&&you[i]<NXT[i]) q.push(i),ok[i]=1;
	}
	while (!q.empty()) {
		int y=q.front(); q.pop();
		int x=zuo[y],z=you[y],a=PRE[y],b=NXT[y];
		//printf("%d %d %d %d %d\n",a,x,y,z,b);
		while (pre[y]!=x) del(pre[y]);
		//printf("HI\n");
		while (nxt[y]!=z) del(nxt[y]);
		//printf("HI2\n");
		del(y);
		if (you[a]>=n||!alive[you[a]]) you[a]=you[y];
		if (zuo[b]<0||!alive[zuo[b]]) zuo[b]=zuo[y];
		if (!ok[a]&&zuo[a]>PRE[a]&&you[a]<NXT[a]) q.push(a),ok[a]=1;
		if (!ok[b]&&zuo[b]>PRE[b]&&you[b]<NXT[b]) q.push(b),ok[b]=1;
	}
	//for (int i=0;i<n;i++) printf("%d ",alive[i]); puts("");
	for (int i=0;i<n;i++) if (alive[i]) {
		//printf("%d\n",i);
		Remove(i);
	}
	
}

• Subtask 1: 5 / 5
• Subtask 2: 35 / 95