Submission #974079

#	Time	Username	Problem	Language	Result	Execution time	Memory
974079		Ooops_sorry	Stray Cat (JOI20_stray)	C++14	100 / 100	47 ms	16736 KiB

Anthony

#ifndef LOCAL
  #include "Anthony.h"
#endif 
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double 

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e4 + 10;
vector<pair<int, int>> g[N];

vector<int> res;

string s = "100110100110", rev_s = "011001011001";

void dfs(int v, int p, int pos) {
  if (v == 0) {
    for (auto [u, i] : g[v]) {
      res[i] = 1;
      dfs(u, v, 1);
    } 
  } else {
    int last = s[pos + 5] - '0';
    if (g[v].size() >= 3) {
      for (auto [u, i] : g[v]) {
        if (u != p) {
          res[i] = last ^ 1;
          dfs(u, v, last ^ 1);
        }
      }
    } else {
      for (auto [u, i] : g[v]) {
        if (u != p) {
          res[i] = s[pos] - '0';
          dfs(u, v, (pos + 1) % 6);
        }
      }
    }
  }
}

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
  for (int i = 0; i < m; i++) {
    g[u[i]].pb({v[i], i});
    g[v[i]].pb({u[i], i});
  }
  if (a >= 3) {
    vector<int> d(n, -1);
    d[0] = 0;
    deque<int> q{0};
    while (q.size() > 0) {
      int v = q.front();
      q.pop_front();
      for (auto [u, i] : g[v]) {
        if (d[u] == -1) {
          d[u] = d[v] + 1;
          q.pb(u);
        }
      }
    }
    vector<int> ans(m, -1);
    for (int v = 0; v < n; v++) {
      for (auto [u, i] : g[v]) {
        if (d[u] == d[v]) {
          ans[i] = d[u] % 3;
        } else {
          ans[i] = min(d[u], d[v]) % 3;
        }
      }
    }
    return ans;
  } else {
    res.resize(m, -1);
    dfs(0, -1, -1);
    return res;
  }
}

Catherine

#ifndef LOCAL
  #include "Catherine.h"
#endif 
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double 

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int A, B;

void Init(int A_, int B_) {
  A = A_;
  B = B_;
}

string kek = "";
bool top = 0;
int last = -1;

string s = "100110100110", rev_s = "011001011001";

bool in(string s, string t) {
  for (int i = 0; i + t.size() <= s.size(); i++) {
    if (s.substr(i, (int)t.size()) == t) {
      return 1;
    }
  }
  return 0;
}

int Move(std::vector<int> y) {
  if (A >= 3) {
    for (int i = 0; i < 3; i++) {
      if (y[i] > 0 && y[(i + 1) % 3] > 0) {
        return i;
      }
    }
    for (int i = 0; i < 3; i++) {
      if (y[i] > 0) {
        return i;
      }
    }
  } else {
    vector<int> y_new = y;
    if (last != -1) {
      y_new[last]++;
    }
    if (y_new[0] + y_new[1] > 2) {
      if (y_new[0] == 1) {
        last = 0;
      } else {
        last = 1;
      }
      top = 1;
      if (y[last] == 0) return -1;
      return last;
    }
    if (top) {
      if (y[0] > 0) {
        last = 0;
      } else {
        last = 1;
      }
      return last;
    }
    if (y[0] + y[1] == 2) {
      if (y[0] > 0 && y[1] > 0) {
        kek += "01";
        last = 1;
        return last;
      } else if (y[0] > 0) {
        kek += "00";
        last = 0;
        return last;
      } else {
        kek += "11";
        last = 1;
        return last;
      }
    } else if (y[0] + y[1] == 1) {
      if (y[0] > 0) {
        kek += "0";
      } else {
        kek += "1";
      }
      if (!in(rev_s, kek)) {
        assert(in(s, kek));
        top = 1;
        return -1;
      } else if (!in(s, kek)) {
        assert(in(rev_s, kek));
        top = 1;
        last = kek.back() - '0';
        return last;
      } else {
        last = kek.back() - '0';
        return last;
      }
    } else {
      top = 1;
      return -1;
    }
  }
  assert(0);
}

Compilation message (stderr)

Anthony.cpp: In function 'void dfs(int, int, int)':
Anthony.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [u, i] : g[v]) {
      |               ^
Anthony.cpp:43:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp:50:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:72:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp:81:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |       for (auto [u, i] : g[v]) {
      |                 ^

• 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