Submission #600698

#	Time	Username	Problem	Language	Result	Execution time	Memory
600698		cadmiumsky	Stray Cat (JOI20_stray)	C++14	100 / 100	200 ms	16444 KiB

Anthony

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

const int nmax = 2e4 + 5;
using pii = pair<int,int>;
vector<int> rez;

//001011 101100


namespace {
  #define F nustiusacompilezcodurilol
  const string F = "001011001011";
  vector<pii> g[nmax];
  int p[nmax];
  void dfs(int node, int f = 0, int state = -1) {
    if(g[node].size() - (node != f) == 1) {
      if(state == -1) {
        if(p[node] == 0)
          state = 1;
        else
          state = 3;
      }
      else
        state = (state + 1) % 12;
    }
    else 
      state = -1;
    for(int i = 0; i < g[node].size(); i++) {    
      int x, e;
      tie(e, x) = g[node][i];
      if(x == f)
        swap(g[node][i], g[node].back()),
        g[node].pop_back(),
        i--;
      else {
        if(state == -1)
          rez[e] = p[node] ^ 1;
        else 
          rez[e] = F[state] - '0';    
        p[x] = rez[e];
        dfs(x, node, state);
      }
    }
    return;
  }
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  rez.resize(M, -1);
  for (int i = 0; i < M; ++i) {
    g[U[i]].emplace_back(i, V[i]);
    g[V[i]].emplace_back(i, U[i]);
  }
  if(A > 2) {
    queue<int> que;
    vector<int> occ(N, 0);
    que.push(0);
    occ[0] = 3;
    while(!que.empty()) {
      int node = que.front(), mine = occ[node] - 1;
      //cerr << node << ' ' << occ[node] << '\n';
      que.pop();
      for(auto [e, x] : g[node]) {
        rez[e] = rez[e] == -1? (mine + 1) % 3 : rez[e];
        if(occ[x] == 0) {
          occ[x] = rez[e] + 1;
          que.push(x);
        } 
      }
    }
    //for(int i = 0; i < M; i++) {
      //cerr << rez[i] << ' ' << U[i] << ' ' << V[i] << '\n';
    //}
  }
  else {
    dfs(0);
    for(int i = 0; i < M; i++) {
      cerr << rez[i] << ' ' << U[i] << ' ' << V[i] << '\n';
    }
  }
  return rez;
}
#undef F

Catherine

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

namespace {
  const string F = "001011001011";

  int A, B;
  int variable_example = 0;
  unordered_set<string> goodstrings;
  void initgs() {
    string s = F + F;
    reverse(s.begin(), s.end());
    int n = F.size();
    for(int i = 0; i < n; i++) {
      goodstrings.insert(s.substr(i, 5));
    }
    return;
  }
  int timer, lastval = -1;
  int state = 0;
  string curr = "";
  int gsum(vector<int> v) { return accumulate(v.begin(), v.end(), 0); }

} 
int amogii = -1;
// 0 - 1 - 1 - 0 - 0 - 1 - 0 - 1 - 1 - 0 - 0 - 1 - 0 - 1 - 1 - 0 - 0 - 1 -

void Init(int A, int B) {
  ::A = min(3, A);
  ::B = B;
  initgs();
}

int Move(std::vector<int> v) {
  int sum = gsum(v);
  if(A == 2) {
    if(state == -1) {
      if(sum == 0)
        return -1; // ???
      else if(lastval == -1 || sum == 1) {
        if(v[0] > 0) return lastval = 0;
        return lastval = 1;
      }
      else
        return lastval ^= 1;
    }
    if(state == 0) {
      if(sum == 1) {
        int ptr = 0;
        for(int i = 0; i < A; i++)
          if(v[i] != 0) {
            lastval = i;
            break;
          }
        state = -1;
        return lastval;
      }
      if(sum == 2) {
        state = 1;
        if(v[1] == 0) {
          curr = "00";
          return lastval = 0;
        }
        if(v[1] == 1) {
          curr = "01";
          return lastval = 1;
        }
        curr = "11";
        return lastval = 1;
      }
      else {
        for(int i = 0; i < A; i++)
          if(v[i] == 1) {
            lastval = i;
            break;
          }
        state = -1;
        return lastval;
      }
    }
    if(state <= 3) {
      if(sum == 0) {
        state = -1;
        return -1;
      }
      if(sum > 1) {
        state = -1;
        if(v[lastval] == 0) {
          return -1;
        }
        return lastval ^= 1;
      }
      else {
        if(v[0] == 1) curr += '0';
        else curr += '1';
        if(state == 3) {
          state = -1;
          if(goodstrings.count(curr))
            return lastval = curr.back() - '0';
          return -1;
        }
        else {
          state++;
          return lastval = curr.back() - '0';
        }
      }
    }
    return -1;
  }
  else {
    int cnt = 0;
    for(auto x : v)
      if(x != 0)
        cnt++;
    if(cnt == 0)
      return -1;
    else if(cnt == 1) {
      if(v[0] != 0) return 0;
      if(v[1] != 0) return 1;
      if(v[2] != 0) return 2;
      //for(auto x : v)
        //cerr << x << ' ';
      //cerr << '\n';
    }
    else { // X --0-- Y --1-- Z --2-- T --0-- U
      if(v[0] == 0) return 1;
      if(v[1] == 0) return 2;
      if(v[2] == 0) return 0;
    }
    while(1);
  }
}

  

Compilation message (stderr)

Anthony.cpp: In function 'void {anonymous}::dfs(int, int, int)':
Anthony.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:66:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |       for(auto [e, x] : g[node]) {
      |                ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:50:13: warning: unused variable 'ptr' [-Wunused-variable]
   50 |         int ptr = 0;
      |             ^~~
Catherine.cpp: At global scope:
Catherine.cpp:20:7: warning: '{anonymous}::timer' defined but not used [-Wunused-variable]
   20 |   int timer, lastval = -1;
      |       ^~~~~
Catherine.cpp:9:7: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    9 |   int variable_example = 0;
      |       ^~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9