oj.uz

답안 #400929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400929 2021-05-08T20:51:08 Z 12tqian 길고양이 (JOI20_stray) C++17
15 / 100
 71 ms 17532 KB 
#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];
        assert(u < n);
        assert(v < n);
        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 {
        assert(n - 1 == m);
        vi par(n);
        int cnt = 0;
        function<void(int, int)> dfs_precomp = [&](int u, int p) {
            assert(u < n);
            par[u] = p;
            cout << u << endl;
            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;
}


#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 {
            if (use[1] == 2) {
                F();
            } else {
                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

Anthony.cpp: In function 'vi Mark(int, int, int, int, vi, vi)':
Anthony.cpp:74:13: warning: unused variable 'cnt' [-Wunused-variable]
   74 |         int cnt = 0;
      |             ^~~

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

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 16416 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 50 ms 16332 KB Output is correct
4 Correct 69 ms 17532 KB Output is correct
5 Correct 71 ms 17444 KB Output is correct
6 Correct 62 ms 16092 KB Output is correct
7 Correct 56 ms 16108 KB Output is correct
8 Correct 63 ms 16856 KB Output is correct
9 Correct 64 ms 16908 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 16416 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 50 ms 16332 KB Output is correct
4 Correct 69 ms 17532 KB Output is correct
5 Correct 71 ms 17444 KB Output is correct
6 Correct 62 ms 16092 KB Output is correct
7 Correct 56 ms 16108 KB Output is correct
8 Correct 63 ms 16856 KB Output is correct
9 Correct 64 ms 16908 KB Output is correct
10 Correct 53 ms 14276 KB Output is correct
11 Correct 55 ms 14224 KB Output is correct
12 Correct 56 ms 14172 KB Output is correct
13 Correct 53 ms 14048 KB Output is correct
14 Correct 61 ms 14364 KB Output is correct
15 Correct 59 ms 14728 KB Output is correct
16 Correct 62 ms 17076 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14008 KB Output is correct
2 Correct 2 ms 736 KB Output is correct
3 Correct 52 ms 13828 KB Output is correct
4 Correct 65 ms 15280 KB Output is correct
5 Correct 63 ms 15292 KB Output is correct
6 Correct 55 ms 14052 KB Output is correct
7 Correct 54 ms 13984 KB Output is correct
8 Correct 61 ms 14592 KB Output is correct
9 Correct 60 ms 14640 KB Output is correct
10 Correct 57 ms 14356 KB Output is correct
11 Correct 61 ms 14496 KB Output is correct
12 Correct 56 ms 14356 KB Output is correct
13 Correct 57 ms 14416 KB Output is correct
14 Correct 62 ms 14628 KB Output is correct
15 Correct 60 ms 14600 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14008 KB Output is correct
2 Correct 2 ms 736 KB Output is correct
3 Correct 52 ms 13828 KB Output is correct
4 Correct 65 ms 15280 KB Output is correct
5 Correct 63 ms 15292 KB Output is correct
6 Correct 55 ms 14052 KB Output is correct
7 Correct 54 ms 13984 KB Output is correct
8 Correct 61 ms 14592 KB Output is correct
9 Correct 60 ms 14640 KB Output is correct
10 Correct 57 ms 14356 KB Output is correct
11 Correct 61 ms 14496 KB Output is correct
12 Correct 56 ms 14356 KB Output is correct
13 Correct 57 ms 14416 KB Output is correct
14 Correct 62 ms 14628 KB Output is correct
15 Correct 60 ms 14600 KB Output is correct
16 Correct 54 ms 12648 KB Output is correct
17 Correct 56 ms 12628 KB Output is correct
18 Correct 52 ms 12288 KB Output is correct
19 Correct 51 ms 12296 KB Output is correct
20 Correct 56 ms 12952 KB Output is correct
21 Correct 53 ms 12528 KB Output is correct
22 Correct 57 ms 14964 KB Output is correct
23 Correct 52 ms 12432 KB Output is correct
24 Correct 51 ms 12416 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 624 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 4140 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 4240 KB Program didn't exit properly, or you printed something to stdout.
2 Halted 0 ms 0 KB -