Submission #1133106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133106		daoquanglinh2007	Ancient Machine (JOI21_ancient_machine)	C++20	0 / 100	27 ms	2376 KiB

Anna

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

void Anna(int N, std::vector<char> S) {
  for (char c : S){
      if (c == 'X'){
        Send(0);
        Send(0);
      }
      else if (c == 'Y'){
        Send(0);
        Send(1);
      }
      else{
        Send(1);
        Send(0);
      }
  } 
}

Bruno

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

const int NM = 18;

string S;
int dp[NM+5][NM+5];

void trace(int i, int j){
  if (i > j) return;
  if (i == j){
    Remove(i);
    return;
  }
  if (dp[i][j] == dp[i+1][j]){
    trace(i+1, j);
    return;
  }
  if (dp[i][j] == dp[i][j-1]){
    trace(i, j-1);
    return;
  }
  for (int k = i+1; k < j; k++){
    if (S[k] != 'Y') continue;
    if (1+(i+1 <= k-1 ? dp[i+1][k-1] : 0)+(k+1 <= j-1 ? dp[k+1][j-1] : 0) != dp[i][j]) continue;
    trace(i+1, k-1);
    trace(k+1, j-1);
    Remove(k);
    Remove(i);
    Remove(j);
    break;
  }
}

void Bruno(int N, int L, std::vector<int> A) {
  assert(L == 2*N);
  S = "";
  for (int i = 0; i < L; i += 2){
    if (A[i] == 0 && A[i+1] == 0) S.push_back('X');
    else if (A[i] == 0 && A[i+1] == 1) S.push_back('Y');
    else S.push_back('Z');
  }
  for (int i = 0; i < N; i++) dp[i][i] = 0;
  for (int i = N-1; i >= 1; i--)
    for (int j = i+1; j <= N; j++){
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      if (S[i] == 'X' && S[j] == 'Z'){
        for (int k = i+1; k < j; k++){
          if (S[k] != 'Y') continue;
          dp[i][j] = max(dp[i][j], 1+(i+1 <= k-1 ? dp[i+1][k-1] : 0)+(k+1 <= j-1 ? dp[k+1][j-1] : 0));
        }
      }
    }
  trace(0, N-1);
}

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