답안 #986366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986366	2024-05-20T11:19:54 Z	cig32	Ancient Machine (JOI21_ancient_machine)	C++17	40 / 100	67 ms	10328 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);
  // 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() != seq[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:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for(int i=1; i<seq.size(); i++) {
      |                ~^~~~~~~~~~~
Bruno.cpp:128:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   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

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	784 KB	Output is correct
2	Correct	0 ms	780 KB	Output is correct
3	Correct	0 ms	796 KB	Output is correct
4	Correct	0 ms	784 KB	Output is correct
5	Correct	0 ms	784 KB	Output is correct
6	Correct	0 ms	784 KB	Output is correct
7	Correct	0 ms	844 KB	Output is correct
8	Correct	0 ms	784 KB	Output is correct
9	Correct	0 ms	784 KB	Output is correct
10	Correct	0 ms	796 KB	Output is correct
11	Correct	0 ms	784 KB	Output is correct

Subtask #2

35.0 / 95.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	55 ms	9364 KB	Partially correct
2	Partially correct	57 ms	9464 KB	Partially correct
3	Partially correct	55 ms	9392 KB	Partially correct
4	Partially correct	58 ms	9512 KB	Partially correct
5	Partially correct	55 ms	9400 KB	Partially correct
6	Partially correct	55 ms	9648 KB	Partially correct
7	Partially correct	56 ms	9348 KB	Partially correct
8	Partially correct	57 ms	9352 KB	Partially correct
9	Partially correct	56 ms	9972 KB	Partially correct
10	Partially correct	55 ms	9492 KB	Partially correct
11	Partially correct	56 ms	9448 KB	Partially correct
12	Partially correct	64 ms	9428 KB	Partially correct
13	Partially correct	55 ms	10328 KB	Partially correct
14	Partially correct	54 ms	9844 KB	Partially correct
15	Partially correct	51 ms	9592 KB	Partially correct
16	Partially correct	53 ms	10132 KB	Partially correct
17	Partially correct	61 ms	9184 KB	Partially correct
18	Partially correct	55 ms	9472 KB	Partially correct
19	Partially correct	57 ms	9092 KB	Partially correct
20	Partially correct	49 ms	10084 KB	Partially correct
21	Partially correct	49 ms	10116 KB	Partially correct
22	Partially correct	55 ms	9144 KB	Partially correct
23	Partially correct	53 ms	9664 KB	Partially correct
24	Partially correct	57 ms	9524 KB	Partially correct
25	Partially correct	56 ms	9168 KB	Partially correct
26	Partially correct	54 ms	9144 KB	Partially correct
27	Partially correct	54 ms	9120 KB	Partially correct
28	Partially correct	66 ms	9184 KB	Partially correct
29	Partially correct	67 ms	9208 KB	Partially correct
30	Partially correct	55 ms	9256 KB	Partially correct
31	Partially correct	55 ms	9120 KB	Partially correct
32	Partially correct	60 ms	9588 KB	Partially correct
33	Partially correct	57 ms	9644 KB	Partially correct