Submission #400894

#	Time	Username	Problem	Language	Result	Execution time	Memory
400894		12tqian	Stray Cat (JOI20_stray)	C++17	15 / 100	66 ms	20772 KiB

Anthony

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

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;

// 0 -> 1 -> 2

vi Mark(int n, int m, int a, int b, vi U, vi V) {
    vector<vi> g(n);
    auto cp = [&](int u, int v) -> pi {
        if (u > v) swap(u, v);
        return mp(u, v);
    };
    map<pi, int> conv;
    vpi ed;
    vi res(m);
    f0r(i, m) {
        int u = U[i];
        int v = V[i];
        conv[cp(u, v)] = i;
        g[u].pb(v);
        g[v].pb(u);
        ed.pb(cp(u, v));
    }
    if (a >= 3) { // bfs work
        vi dist(n, -1);
        list<int> que;
        dist[0] = 0;
        que.pb(0);
        while (!que.empty()) {
            int u = que.front();
            que.pop_front();
            each(v, g[u]) {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                que.push_back(v);
            }
        }
        each(e, ed) {
            int u = e.f;
            int v = e.s;
            int id = conv[cp(u, v)];
            if (dist[u] == dist[v]) {
                res[id] = dist[u] % 3;
            } else {
                if (dist[u] > dist[v]) {
                    swap(u, v);
                }
                res[id] = dist[u] % 3;
            }
        }
    } else {
        vi par(n);
        function<void(int, int)> dfs_precomp = [&](int u, int p) {
            par[u] = p;
            each(v, g[u]) {
                if (v == p) continue;
                dfs_precomp(v, u);
            }
        };
        dfs_precomp(0, -1);
        vi lab(n);
        function<void(int, int, int)> dfs_label = [&](int u, int p, int d) {
            if (u == 0) {
                each(v, g[u]) {
                    if (v == p) continue;
                    lab[v] = 0;
                    dfs_label(v, u, 0);
                }
                return;
            }
            if (sz(g[u]) == 1) return;
            if (sz(g[u]) > 2) {
                each(v, g[u])  {
                    if (v == p) continue;
                    lab[v] = lab[u] ^ 1;
                    dfs_label(v, u, 0);
                }
            } else {
                each(v, g[u]) {
                    if (v == p) continue;
                    if (d == 0 || d == 2 || d == 5) {
                        lab[v] = lab[u] ^ 1;
                    } else {
                        lab[v] = lab[u];
                    }
                    dfs_label(v, u, (d + 1) % 6);
                }
            }
        };
        dfs_label(0, -1, -1);
        f1r(i, 1, n) {
            int id = conv[cp(i, par[i])];
            res[id] = lab[i];
        }
    }
    return res;
}

Catherine

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

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;

namespace {

int a, b;
vi moves; 
vpi seen;
bool oriented = false;

}  // namespace

void Init(int A, int B) {
    ::a = A;
    ::b = B;
}

int MoveT(vi& v) { 
    int x = v[0]; 
    int y = v[1];
    
    pi use = {x, y};
   
    if (sz(moves)) {
        if (moves.back() == 0) use.f++;
        else use.s++;
    }

    seen.pb(use);

    #define R(k) moves.pb(k); return k;
    #define F() if (x) { R(0); } else { R(1); }
    // R is for moving to a color
    // F is if you're on a line, move forward

    if (oriented) { // if you're already oriented
        if (x == 0) {
            R(1);
        } else if (y == 0) {
            R(0);
        }
        if (x > y) {
            R(1);
        } else if (x < y) {
            R(0);
        }
        assert(false);
        R(-1); // shouldn't reach here
    }

    { // checking if you're already at a good place
        if (x == 0 && y == 0) { // dead end leaf node
            R(-1);
        }

        if (sz(moves)) {
            if (moves.back() == 0) x++;
            else y++;
        }
        
        if (x == 0 && y == 1) { // leaf nodes
            oriented = true;
            R(1);
        } else if (y == 0 && x == 1) {
            oriented = true;
            R(0);
        } 
        
        if (x > y) { // you already reached a good place
            oriented = true;
            if (sz(moves)) {
                if (moves.back() == 0) x--;
                else y--;
            }
            if (y == 0) {
                R(-1);
            }
            else {
                R(1);
            } 
        } else if (x < y) {
            oriented = true;
            if (sz(moves)) {
                if (moves.back() == 0) x--;
                else y--;
            }
            if (x == 0) {
                R(-1); 
            } else {
                R(0);
            }
        }

        if (sz(moves)) {
            if (moves.back() == 0) x--;
            else y--;
        }
    }


    int did = sz(moves);

    if (did == 0) { // first move
        F();
    } else if (did == 1) { 
        if (seen[0].f == seen[0].s) { // 0 1, went 0 before
            if (x) { // go 0 if possible
                R(0);
            } else {
                R(-1);
            }
        } else { // same things
            if (moves.back() == 0 && x) {
                R(-1);
            } else if (moves.back() == 1 && y) {
                R(-1);
            } else {
                F();
            }
        }
    } else if (did == 2) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 3) {
        if (moves.back() == -1) {
            R(-1);
        } else {
            F();
        }
    } else if (did == 4) {
        if (moves.back() == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 5) {
        R(-1);
    } else if (did == 6) {
        oriented = true;
        vi came; // direction just came from
        vi other; // other direction
        { // came
            if (moves[4] == -1 && moves[5] == -1) {
                came.pb(moves[2]);
                came.pb(moves[3]);
                if (seen[4].f >= 2) {
                    came.pb(0);
                } else if (seen[4].s >= 2) {
                    came.pb(1);
                } else {
                    came.pb(came.back() ^ 1);
                }
            } else {
                came.pb(moves[4]); 
                if (seen[5].f >= 2) {
                    came.pb(0);
                } else if (seen[5].s >= 2) {
                    came.pb(1);
                } else {
                    came.pb(came.back() ^ 1);
                }
            }
        }
        { // other
            if (moves[0] != -1 && moves[1] != -1) {
                other.pb(moves[0]);
                other.pb(moves[1]);
                if (seen[2].f >= 2) {
                    other.pb(0);
                } else if (seen[2].s >= 2) {
                    other.pb(1);
                } else {
                    other.pb(other.back() ^ 1);
                }
            } else {
                other.pb(moves[0]);
                if (seen[1].f >= 2) {
                    other.pb(0);
                } else if (seen[1].s >= 2) {
                    other.pb(1);
                } else {
                    other.pb(other.back() ^ 1);
                }
            }
        }
        vi comb = came;
        reverse(all(comb));
        each(x, other) comb.pb(x);
        vi use;
        int i1 = 0;
        int i2 = 0;
        int sz = sz(comb);
        while (i1 != sz) {
            while (i2 < sz - 1 && comb[i2 + 1] == comb[i2]) ++i2;
            use.pb(i2 - i1 + 1);
            i1 = ++i2;
        }
        int num = 0;
        each(x, use) x += num;
        
        assert(num == 5);

        if (sz(use) == 2) {
            int x = use[0];
            int y = use[1];
            if (x == 2) {
                R(-1);
            } else {
                F();
            } 
        } else if (sz(use) == 3) {
            int x = use[0];
            int y = use[1];
            int z = use[2];
            if (x == 1) {
                if (y == 2) {
                    R(-1);
                } else if (y == 1) {
                    F();
                } else {
                    assert(false);
                }
            } else if (x == 2) {
                if (y == 2) {
                    F();
                } else {
                    assert(false);
                }
            } else if (x == 3) {
                R(-1);
            }
        }
    } else {
        while (true) {}
        assert(false);
    }
    assert(false);
    R(-1);
}

int MoveG(vi& y) {
    int a0 = y[0];
    int a1 = y[1];
    int a2 = y[2];
    if (a0 && a1) {
        return 0;
    } else if (a1 && a2) {
        return 1;
    } else if (a2 && a0) {
        return 2;
    } else if (a0) {
        return 0;
    } else if (a1) {
        return 1;
    } else if (a2) {
        return 2;
    }
    return -1;
}

int Move(vi y) {
    if (a >= 3) {
        return MoveG(y);
    } else {
        return MoveT(y);    
    }
}

Compilation message (stderr)

Catherine.cpp: In function 'int MoveT(vi&)':
Catherine.cpp:227:17: warning: unused variable 'y' [-Wunused-variable]
  227 |             int y = use[1];
      |                 ^
Catherine.cpp:236:17: warning: unused variable 'z' [-Wunused-variable]
  236 |             int z = use[2];
      |                 ^

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