Submission #708758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708758	2023-03-12T09:09:59 Z	ntdxl05	Ancient Machine (JOI21_ancient_machine)	C++17	0 / 100	79 ms	10744 KB

Anna
Bruno

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

namespace {

int variable_example = 0;

}

void Anna(int N, std::vector<char> S) {
const int dc[] = {'X', 'Y', 'Z'};
int idc[256];
  for (int i = 0; i < 3; i++) idc[dc[i]] = i;
  for (int i = 0; i < N; i++) {
    Send(idc[S[i]] >> 1 & 1);
    Send(idc[S[i]] & 1);
  }
}

#include <bits/stdc++.h>
#include "Bruno.h"
#include <vector>

using namespace std;

namespace {

// int variable_example = 0;

const int inf = 1e9;

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

template<class U, class V>
bool minz(U &a, V b) {
  if (a > b) return a = b, 1;
  return 0;
}
template<class U, class V>
bool maxz(U &a, V b) {
  if (a < b) return a = b, 1;
  return 0;
}

}  // namespace

void Bruno(int N, int L, std::vector<int> A) {
const int dc[] = {'X', 'Y', 'Z'};
int idc[256];
  for (int i = 0; i < L; i++) {
    // variable_example += FunctionExample(A[i]);
  }

  vector<char> S(N);
  for (int i = 0; i < N; i++) S[i] = dc[A[i << 1] << 1 | A[i << 1 | 1]];
  // vector<int> dp(1 << N, -inf), trc(1 << N, -1);
  // dp[0] = 0;
  // for (int msk = 0; msk < (1 << N) - 1; msk++) {
  //   vector<int> b(N);
  //   for (int i = 0; i < N; i++) b[i] = msk >> i & 1;
  //   for (int i = 0; i < N; i++) {
  //     if (b[i]) continue;
  //     int l = i - 1, r = i + 1;
  //     for (; ~l && !b[l]; l--);
  //     for (; r < N && !b[r]; r++);
  //     bool e = ~l && r < N && S[i] == 'Y' && S[l] == 'X' && S[r] == 'Z';
  //     if (maxz(dp[msk | 1 << i], dp[msk] + e)) trc[msk | 1 << i] = i;
  //   }
  // }

  // int cr = (1 << N) - 1;
  // while (cr) {
  //   auto &t = trc[cr];
  //   Remove(t);
  //   cr ^= 1 << t;
  // }

  while (S.size() && S.back() ^ 'Z') {
    Remove(S.size() - 1);
    S.pop_back();
  }
  int p = 0;
  for (; p < S.size() && S[p] ^ 'X'; p++) Remove(p);
  if ((int)S.size() - p < 3) {
    for (int i = 0; i < S.size(); i++) Remove(i);
    return ;
  }
  // cerr << N << "\n"; cerr << p << " "; for (auto c: S) cout << c; cout << "\n";
  vector<int> vv;
  for (int i = p; i < S.size(); i++) {
    if (!vv.size() || ((S[vv.back()] != 'Y') ^ (S[i] != 'Y'))) vv.push_back(i);
    else if (i < S.size() - 1) Remove(i);
  }
  if (vv.back() < S.size() - 1) {
    Remove(vv.back());
    vv.back() = S.size() - 1;
  }
  // for (auto v: vv) cerr << v << " "; cerr << "\n";
  // return ;

  vector<int> Lf(N, -1), Rt(N, N), used(N);
  set<int> st;
  for (int i = 0; i < vv.size(); i++) {
    if (!(S[vv[i]] ^ 'Y') && !(S[vv[i - 1]] ^ 'X') && !(S[vv[i + 1]] ^ 'Z')) st.insert(vv[i]);
    if (i) Lf[vv[i]] = vv[i - 1];
    if (i < vv.size() - 1) Rt[vv[i]] = vv[i + 1];
  }
  while (st.size()) {
    int u = *begin(st); st.erase(begin(st));
    if (used[u]) continue;
    Remove(u); used[u] = 1;
    // cerr << u << "\n";
    int v = Rt[Rt[u]];
    if (v < N) {
      Remove(Rt[u]); used[Rt[u]] = 1;
      // cerr << "R " << Rt[u] << "\n";
      Lf[v] = Lf[u];
      Rt[Lf[u]] = v;
      if (!(S[Rt[v]] ^ 'Z')) st.insert(v);
    }
    else {
      Remove(Lf[u]); used[Lf[u]] = 1;
      // cerr << "L " << Lf[u] << "\n";
      v = Lf[Lf[u]];
      if (~v) {
        Rt[v] = Rt[u];
        Lf[Rt[u]] = v;
        if (!(S[Lf[v]] ^ 'X')) st.insert(v);
      }
    }
  }

  for (auto v: vv) {
    if (!used[v]) {
      // cerr << "O " << v << "\n";
      Remove(v);
    }
  }
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:17:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |     Send(idc[S[i]] >> 1 & 1);
      |                  ^
Anna.cpp:18:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |     Send(idc[S[i]] & 1);
      |                  ^
Anna.cpp: At global scope:
Anna.cpp:8:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    8 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Bruno.cpp: In function 'void Bruno(int, int, std::vector<int>)':
Bruno.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (; p < S.size() && S[p] ^ 'X'; p++) Remove(p);
      |          ~~^~~~~~~~~~
Bruno.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < S.size(); i++) Remove(i);
      |                     ~~^~~~~~~~~~
Bruno.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for (int i = p; i < S.size(); i++) {
      |                   ~~^~~~~~~~~~
Bruno.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     else if (i < S.size() - 1) Remove(i);
      |              ~~^~~~~~~~~~~~~~
Bruno.cpp:75:17: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   if (vv.back() < S.size() - 1) {
      |       ~~~~~~~~~~^~~~~~~~~~~~~~
Bruno.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i < vv.size(); i++) {
      |                   ~~^~~~~~~~~~~
Bruno.cpp:87:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     if (i < vv.size() - 1) Rt[vv[i]] = vv[i + 1];
      |         ~~^~~~~~~~~~~~~~~
Bruno.cpp:30:5: warning: unused variable 'idc' [-Wunused-variable]
   30 | int idc[256];
      |     ^~~
Bruno.cpp: At global scope:
Bruno.cpp:13:5: warning: 'int {anonymous}::FunctionExample(int)' defined but not used [-Wunused-function]
   13 | int FunctionExample(int P) { return 1 - P; }
      |     ^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	508 KB	Output is correct
2	Correct	516 KB	Output is correct
3	Correct	508 KB	Output is correct
4	Correct	508 KB	Output is correct
5	Correct	516 KB	Output is correct
6	Correct	508 KB	Output is correct
7	Correct	508 KB	Output is correct
8	Incorrect	520 KB	Wrong Answer [4]
9	Halted	0 KB	-

Subtask #2
0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	70 ms	10504 KB	Partially correct
2	Partially correct	73 ms	10532 KB	Partially correct
3	Partially correct	72 ms	10556 KB	Partially correct
4	Partially correct	73 ms	10524 KB	Partially correct
5	Partially correct	79 ms	10516 KB	Partially correct
6	Partially correct	73 ms	10508 KB	Partially correct
7	Partially correct	73 ms	10532 KB	Partially correct
8	Partially correct	72 ms	10636 KB	Partially correct
9	Partially correct	75 ms	10488 KB	Partially correct
10	Partially correct	71 ms	10560 KB	Partially correct
11	Partially correct	75 ms	10540 KB	Partially correct
12	Partially correct	77 ms	10572 KB	Partially correct
13	Partially correct	78 ms	10688 KB	Partially correct
14	Partially correct	79 ms	10744 KB	Partially correct
15	Partially correct	70 ms	10512 KB	Partially correct
16	Partially correct	67 ms	10540 KB	Partially correct
17	Partially correct	73 ms	9220 KB	Partially correct
18	Partially correct	77 ms	9180 KB	Partially correct
19	Incorrect	70 ms	9172 KB	Wrong Answer [4]
20	Halted	0 ms	0 KB	-

Submission #708758

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 95.0

Subtask #1
0 / 5.0

Subtask #2
0 / 95.0