oj.uz

Submission #946058

# Submission time Handle Problem Language Result Execution time Memory
946058 2024-03-14T09:53:58 Z WongYiKai Ancient Machine (JOI21_ancient_machine) C++17
0 / 100
 242 ms 166028 KB 
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

void Anna(int N, vector<char> S) {
	for (int i=0;i<N;i++){
		if (S[i]=='X'){
			Send(0);
			Send(0);
		}
		else if (S[i]=='Y'){
			Send(0);
			Send(1);
		}
		else{
			Send(1);
			Send(0);
		}
	}
}

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

int n;

vector<int> s;
int dp[500000][20],par[500000][20];

int rec(int r,int last){
	if (dp[r][last]!=-1) return dp[r][last];
	int good=0;
	if (s[last]==2){
		int temp=last;
		int bef=-1;
		while (temp>=0 && temp--){
			if ((r&(1<<temp))==0){
				 bef=temp;
				 break;
			 }
		 }
		 if (bef!=-1){
			 if (s[bef]==3){
				 temp = last;
				 bef=-1;
				 while (temp<n && temp++){
					 if ((r&(1<<temp))==0){
						 bef = temp;
						 break;
					 }
				 }
				 if (bef!=-1){
					 if (s[bef]==1) good=1;
				 }
			 }
		 }
	 }
	 
		
	int ans=-1;
	int p=-1;
	for (int i=0;i<n;i++){
		if (i==last) continue;
		if ((r&(1<<i))==0) continue;
		int nw = r-(1<<last);
		int aa = rec(nw,i)+good;
		if (aa>ans){
			ans = aa;
			p = i;
		}
	}
	dp[r][last] = ans;
	par[r][last] = p;
	if (ans==-1) return 0;
	return ans;
}

void Bruno(int N, int L, vector<int> A) {
	n=N;
	stack<pair<int,int>> d;
	memset(dp,-1,sizeof(dp));
	memset(par,-1,sizeof(par));
	for (int i=0;i<N;i++){
		int ff = A[2*i],fs = A[2*i+1];
		if (ff==0&&fs==0){
			s.push_back(1);
		}
		else if (ff==0&&fs==1) s.push_back(2);
		else s.push_back(3);
	}
	int num=1;
	for (int i=0;i<n;i++){
		num *= 2;
	}
	num--;
	int ans=-1;
	int p=-1;
	for (int i=0;i<n;i++){
		int aa = rec(num,i);
		if (aa>ans){
			ans=aa;
			p=i;
		}
	}
	int nod = p;
	while (p!=-1){
		Remove(p);
		int p2=p;
		p = par[num][p];
		num -= (1<<p2);
	}
			
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:85:6: warning: unused variable 'nod' [-Wunused-variable]
   85 |  int nod = p;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 242 ms 79112 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 166028 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -