Submission #400922

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
400922	2021-05-08T20:31:26 Z	12tqian	Stray Cat (JOI20_stray)	C++17	15 / 100	72 ms	24008 KB

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
        // assert(x || y);
        if (x == 0) {
            R(1);
        } else if (y == 0) {
            R(0);
        }

        if (sz(moves)) {
            if (moves.back() == 0) x++;
            else y++;
        }
        
        if (x > y) {
            assert(y == 1);
            R(1);
        } else if (x < y) {
            assert(x == 1);
            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
            oriented = true;
            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 && y) { // you already reached a good place
            oriented = true;
            assert(y == 1);
            if (sz(moves)) {
                if (moves.back() == 0) x--;
                else y--;
            }
            if (y == 0) {
                R(-1);
            }
            else {
                R(1);
            } 
        } else if (x < y && x) {
            oriented = true;
            assert(x == 1);
            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--;
        }
    }
    // each(x, moves) cout << x << " ";
    // cout << endl;
    // each(x, seen) cout << "(" << x.f << ", " << x.s << ") ";
    // cout << endl;

    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) {
        F();
    } else if (did == 4) {
        if (moves[2] == -1) {
            F();
        } else {
            R(-1);
        }
    } else if (did == 5) {
        if (moves.back() == -1) {
            F();
        } else {
            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);
        // cout << "COMB" << endl;
        // each(x, comb) cout << x << " ";
        // cout << endl;
        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) num += x;
        
        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 {
        assert(false);
    }
    // cout << did << endl;
    // cout << "YA" << endl;
    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

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

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	16404 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	50 ms	16232 KB	Output is correct
4	Correct	71 ms	17616 KB	Output is correct
5	Correct	70 ms	17544 KB	Output is correct
6	Correct	56 ms	16248 KB	Output is correct
7	Correct	55 ms	16128 KB	Output is correct
8	Correct	66 ms	16916 KB	Output is correct
9	Correct	65 ms	16900 KB	Output is correct

Subtask #2

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	16404 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	50 ms	16232 KB	Output is correct
4	Correct	71 ms	17616 KB	Output is correct
5	Correct	70 ms	17544 KB	Output is correct
6	Correct	56 ms	16248 KB	Output is correct
7	Correct	55 ms	16128 KB	Output is correct
8	Correct	66 ms	16916 KB	Output is correct
9	Correct	65 ms	16900 KB	Output is correct
10	Correct	53 ms	14160 KB	Output is correct
11	Correct	56 ms	14352 KB	Output is correct
12	Correct	53 ms	14108 KB	Output is correct
13	Correct	52 ms	14260 KB	Output is correct
14	Correct	54 ms	14352 KB	Output is correct
15	Correct	59 ms	14684 KB	Output is correct
16	Correct	62 ms	16944 KB	Output is correct

Subtask #3

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	13976 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	50 ms	13932 KB	Output is correct
4	Correct	64 ms	15328 KB	Output is correct
5	Correct	65 ms	15372 KB	Output is correct
6	Correct	56 ms	13936 KB	Output is correct
7	Correct	56 ms	13900 KB	Output is correct
8	Correct	60 ms	14564 KB	Output is correct
9	Correct	66 ms	14564 KB	Output is correct
10	Correct	60 ms	14364 KB	Output is correct
11	Correct	56 ms	14344 KB	Output is correct
12	Correct	59 ms	14432 KB	Output is correct
13	Correct	57 ms	14332 KB	Output is correct
14	Correct	61 ms	14536 KB	Output is correct
15	Correct	63 ms	14568 KB	Output is correct

Subtask #4

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	13976 KB	Output is correct
2	Correct	2 ms	488 KB	Output is correct
3	Correct	50 ms	13932 KB	Output is correct
4	Correct	64 ms	15328 KB	Output is correct
5	Correct	65 ms	15372 KB	Output is correct
6	Correct	56 ms	13936 KB	Output is correct
7	Correct	56 ms	13900 KB	Output is correct
8	Correct	60 ms	14564 KB	Output is correct
9	Correct	66 ms	14564 KB	Output is correct
10	Correct	60 ms	14364 KB	Output is correct
11	Correct	56 ms	14344 KB	Output is correct
12	Correct	59 ms	14432 KB	Output is correct
13	Correct	57 ms	14332 KB	Output is correct
14	Correct	61 ms	14536 KB	Output is correct
15	Correct	63 ms	14568 KB	Output is correct
16	Correct	51 ms	12488 KB	Output is correct
17	Correct	55 ms	12528 KB	Output is correct
18	Correct	51 ms	12304 KB	Output is correct
19	Correct	53 ms	12244 KB	Output is correct
20	Correct	57 ms	12844 KB	Output is correct
21	Correct	54 ms	12580 KB	Output is correct
22	Correct	59 ms	14844 KB	Output is correct
23	Correct	53 ms	12304 KB	Output is correct
24	Correct	53 ms	12428 KB	Output is correct

Subtask #5

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	876 KB	Output is correct
2	Correct	2 ms	576 KB	Output is correct
3	Correct	2 ms	872 KB	Output is correct
4	Correct	2 ms	880 KB	Output is correct
5	Correct	2 ms	888 KB	Output is correct
6	Correct	2 ms	884 KB	Output is correct
7	Correct	2 ms	876 KB	Output is correct
8	Correct	2 ms	872 KB	Output is correct
9	Correct	2 ms	960 KB	Output is correct
10	Correct	2 ms	880 KB	Output is correct
11	Correct	2 ms	880 KB	Output is correct
12	Runtime error	3 ms	1264 KB	Execution killed with signal 6
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 71.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	12272 KB	Output is correct
2	Correct	57 ms	14024 KB	Output is correct
3	Correct	2 ms	488 KB	Output is correct
4	Correct	43 ms	11920 KB	Output is correct
5	Correct	63 ms	15964 KB	Output is correct
6	Correct	64 ms	15932 KB	Output is correct
7	Correct	56 ms	15460 KB	Output is correct
8	Correct	53 ms	15204 KB	Output is correct
9	Correct	62 ms	16456 KB	Output is correct
10	Correct	64 ms	16440 KB	Output is correct
11	Correct	62 ms	16368 KB	Output is correct
12	Correct	63 ms	16284 KB	Output is correct
13	Correct	66 ms	16348 KB	Output is correct
14	Correct	63 ms	16300 KB	Output is correct
15	Correct	65 ms	16240 KB	Output is correct
16	Correct	63 ms	16336 KB	Output is correct
17	Correct	61 ms	16088 KB	Output is correct
18	Correct	67 ms	16092 KB	Output is correct
19	Correct	71 ms	15940 KB	Output is correct
20	Correct	60 ms	16040 KB	Output is correct
21	Runtime error	59 ms	24008 KB	Execution killed with signal 6
22	Halted	0 ms	0 KB	-

Subtask #7

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	12224 KB	Output is correct
2	Correct	60 ms	14144 KB	Output is correct
3	Correct	2 ms	496 KB	Output is correct
4	Correct	45 ms	12080 KB	Output is correct
5	Correct	63 ms	15916 KB	Output is correct
6	Correct	72 ms	15972 KB	Output is correct
7	Incorrect	52 ms	15192 KB	Wrong Answer [5]
8	Halted	0 ms	0 KB	-