Submission #513361

#	Time	Username	Problem	Language	Result	Execution time	Memory
513361		wiwiho	Stray Cat (JOI20_stray)	C++14	85 / 100	58 ms	17276 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

using pii = pair<int, int>;

namespace {

    vector<int> magic;
    vector<vector<pii>> g;
    vector<int> ans;

}  // namespace

void dfs(int now, int p, int top, int len){
    int cnt = 0;
    for(pii i : g[now]){
        if(i.F == p) continue;
        cnt++;
    }
    int nxt = !top;
    if(cnt == 1){
        if(len == -1){
            if(top == 0) len = 0;
            else len = 1;
        }
        len++;
        //cerr << "two " << now << " " << len << "\n";
        nxt = magic[len % 6];
    }
    else len = -1;

    for(pii i : g[now]){
        if(i.F == p) continue;
        ans[i.S] = nxt;
        dfs(i.F, now, nxt, len);
    }
}

vector<int> Mark(int n, int m, int A, int B,
                      vector<int> U, vector<int> V) {

    magic = {0, 1, 0, 0, 1, 1};

    ans.resize(m);

    g.resize(n);
    for(int i = 0; i < m; i++){
        int u = U[i], v = V[i];
        g[u].eb(mp(v, i));
        g[v].eb(mp(u, i));
    }

    dfs(0, 0, 1, -1);
    //printv(ans, cerr);

    return ans;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

namespace {

int A, B;
int lst = -1;
vector<int> magic;
deque<int> tmp;

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    magic = {0, 1, 0, 0, 1, 1};
}

bool check(){
    while(tmp.size() > 5) tmp.pop_front();
    if(tmp.size() < 5) return false;

    for(int i = 0; i < 6; i++){
        bool ok = true;
        for(int j = 0; j < 5; j++){
            if(tmp[j] != magic[(i + j) % 6]) ok = false;
        }
        if(ok) return true;
    }
    return false;
}

int Move(vector<int> y) {
    
    if(lst != -1) y[lst]++;
    int deg = 0;
    for(int i : y) deg += i;

    if(deg >= 3){
        int r;
        for(int i = 0; i < 2; i++){
            if(y[i] != 1) continue;
            if(i == lst) r = -1;
            else r = lst = i;
        }
        tmp.clear();
        tmp.eb(lst);
        //cerr << "test " << r << "\n";
        return r;
    }

    int nxt = -1;
    if(lst != -1) y[lst]--;
    for(int i = 0; i < 2; i++){
        if(y[i]){
            nxt = i;
            //break;
        }
    }

    if(lst == -1){
        y[nxt]--;
        for(int i = 0; i < 2; i++){
            if(y[i]){
                tmp.eb(i);
            }
        }
    }

    tmp.eb(nxt);
    //cerr << "check ";
    //printv(tmp, cerr);
    if(check()){
        tmp.clear();
        tmp.eb(lst);
        return -1;
    }

    lst = nxt;
    //cerr << nxt << "\n";

    return nxt;
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:54:13: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         int r;
      |             ^

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