Submission #986349

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
986349	2024-05-20T11:08:38 Z	cig32	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	315 ms	9248 KB

Anna

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

namespace {

int variable_example = 0;

}

void Anna(int N, std::vector<char> S) {
  variable_example++;
  for(int i=0; i<N; i+=10) {
    int ans = 0;
    for(int j=i; j<min(N, i+10); j++) {
      ans *= 3;
      ans += (S[j] == 'X' ? 0 : (S[j] == 'Y' ? 1 : 2));
    }
    for(int j=0; j<16; j++) {
      if(ans & (1<<j)) Send(1);
      else Send(0);
    }
  }
}

/*
g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp
./grader < input.txt
*/

Bruno

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

namespace {

int variable_example = 0;

int FunctionExample(int P) { return 1 - P; }

}  // namespace

void bitmaskDP(string S) {
  int N = S.size();
  int dp[(1 << N)], pre[(1 << N)];
  dp[0] = 0;
  pre[0] = -1;
  for(int i=1; i<(1<<N); i++) {
    dp[i] = -1;
    pre[i] = -1;
    for(int j=0; j<N; j++) {
      if(i & (1 << j)) {
        int msk = i - (1 << j);
        string T;
        for(int k=0; k<N; k++) {
          if(!(msk & (1 << k))) {
            T += S[k];
          }
          if(k == j) {
            T[T.size() - 1] ^= 32;
          }
        }
        if(T.find("XyZ") != string::npos) {
          if(dp[i - (1 << j)] + 1 > dp[i]) {
            dp[i] = dp[i - (1 << j)] + 1;
            pre[i] = i - (1 << j);
          }
        }
        else {
          if(dp[i - (1 << j)] > dp[i]) {
            dp[i] = dp[i - (1 << j)];
            pre[i] = i - (1 << j);
          }
        }
      }
    }
  }
  int cur = (1 << N) - 1;
  vector<int> v;
  while(cur) {
    int bit = cur ^ pre[cur];
    v.push_back(32 - __builtin_clz(bit) - 1);
    cur ^= bit;
  }
  reverse(v.begin(), v.end());
  for(int x: v) Remove(x);
}

void Bruno(int N, int L, std::vector<int> A) {
  
  string S;
  int j = 0;
  for(int i=0; i<L; i+=16) {
    int rem = min(10, N - j);
    j += 10;
    int base = 1;
    for(int k=0; k<rem-1; k++) base *= 3;
    int ans = 0;
    for(int j=i; j<min(L, i+16); j++) {
      if(A[j] == 1) ans += (1 << (j-i));
    }
    for(int j=rem-1; j>=0; j--) {
      int div = ans / base;
      ans %= base;
      base /= 3;
      if(div == 0) S += 'X';
      else if(div == 1) S += 'Y';
      else S += 'Z';
    }
  }
  assert(S.size() == N);
  if(N <= 18) {
    bitmaskDP(S); return;
  }
  // 40 pts solution
  int lb = -1, rb = -1;
  for(int i=0; i<N; i++) {
    if(S[i] == 'X') {
      lb = i; break;
    }
  }
  for(int i=N-1; i>=0; i--) {
    if(S[i] == 'Z') {
      rb = i; break;
    }
  }
  if(lb == -1 || rb == -1 || lb > rb) {
    for(int i=0; i<N; i++) Remove(i);
    return;
  }
  for(int i=0; i<lb; i++) Remove(i);
  for(int i=rb+1; i<N; i++) Remove(i);
  vector<int> seq;
  for(int i=lb; i<=rb; i++) {
    if(i == lb || i == rb) seq.push_back(i);
    else if(S[i] == 'Y' && S[i-1] == 'Y') Remove(i);
    else if(S[i] == 'Y') seq.push_back(i);
    else if(S[i-1] == 'Y') seq.push_back(i);
    else Remove(i);
  }
  vector<int> seq2;
  seq2.push_back(seq[0]);
  for(int i=1; i<seq.size(); i++) {
    seq2.push_back(seq[i]);
    if(S[seq[i-1]] != 'Y' && S[seq[i]] != 'Y') {
      if(i == 1) {
        Remove(seq[i]);
        seq2.pop_back();
      }
      else {
        Remove(seq[i-1]);
        seq2.pop_back();
        seq2.pop_back();
        seq2.push_back(seq[i]);
      }
    }
  }
  seq = seq2; // remainder
  vector<int> stk;
  for(int i=0; i<seq.size(); i++) {
    stk.push_back(seq[i]);
    while(stk.size() >= 3 && S[stk[stk.size() - 3]] == 'X' && S[stk[stk.size() - 2]] == 'Y' && S[stk.back()] == 'Z') {
      Remove(stk[stk.size() - 2]);
      int tp = stk.back();
      stk.pop_back();
      stk.pop_back();
      if(stk.back() > 0) {
        int cur = stk.back();
        Remove(cur);
        stk.pop_back();
        stk.push_back(tp);
      }
      else Remove(tp);
    }
  }
  for(int X: stk) Remove(X);
}

/*
./grader < input.txt


g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp
g++ gen.cpp -std=c++17 -o gen
g++ D.cpp -std=c++17 -o D
g++ C.cpp -std=c++17 -o C
for ((i=1;;++i)); do
  ./gen $i > input.txt
  ./grader < input.txt > bruh.txt
  ./D < input.txt > answer.txt
  ./C < bruh.txt > output.txt
  ./checker
  echo "Passed test: " $i
done

*/

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Bruno.cpp:3:
Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:82:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   assert(S.size() == N);
      |          ~~~~~~~~~^~~~
Bruno.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i=1; i<seq.size(); i++) {
      |                ~^~~~~~~~~~~
Bruno.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(int i=0; i<seq.size(); i++) {
      |                ~^~~~~~~~~~~
Bruno.cpp: At global scope:
Bruno.cpp:10:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   10 | int FunctionExample(int P) { return 1 - P; }
      |     ^~~~~~~~~~~~~~~
Bruno.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	248 ms	2828 KB	Output is correct
2	Correct	263 ms	2840 KB	Output is correct
3	Correct	238 ms	2828 KB	Output is correct
4	Correct	287 ms	2840 KB	Output is correct
5	Correct	280 ms	2828 KB	Output is correct
6	Correct	308 ms	2840 KB	Output is correct
7	Correct	0 ms	792 KB	Output is correct
8	Correct	1 ms	780 KB	Output is correct
9	Correct	315 ms	2836 KB	Output is correct
10	Correct	205 ms	2840 KB	Output is correct
11	Correct	205 ms	2996 KB	Output is correct

Subtask #2

0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	54 ms	9196 KB	Partially correct
2	Incorrect	56 ms	9248 KB	Wrong Answer [6]
3	Halted	0 ms	0 KB	-