Submission #860813

#	Time	Username	Problem	Language	Result	Execution time	Memory
860813		Ellinor	Cop and Robber (BOI14_coprobber)	C++14	16 / 100	32 ms	1736 KiB

coprobber

#include "coprobber.h"

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")

typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back

// inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }

ll INF = 1e15;
ll mod = 1e9 + 7;

// #define int ll
#define float double

int n;
ll m = 0;
vector<vector<int>> adj;
int pat = 0;

int br, he;

int dfs(int node, int par, int r)
{
    int ret = 0;
    if (node == r) ret = 1;

    rep(i,0,adj[node].size()) {
        if (adj[node][i] != par) {
            if (dfs(adj[node][i], node, r)) ret = adj[node][i];
        }
    }

    return ret;
}

int start(int N, bool A[MAX_N][MAX_N])
{
    n = N;
    adj.assign(n, {});
    rep(i,0,n) {
        rep(j,i + 1,n) {
            if (A[i][j]) {
                adj[i].pb(j);
                adj[j].pb(i);
                m++;
            }
        }
    }

    if (m != n - 1) {
        rep(i,1,n) {
            if (adj[i].size() == 2) {
                br = i + 1;
                break;
            }
            he = n / br;
        }
    }

    return 0;
}

int nextMove(int R)
{
    if (pat == R) exit(0); // assert ?
    if (m == n - 1) return pat = dfs(pat, -1, R);
    else 
    {
        int rx = R % br, ry = R / br;
        int px = pat % br, py = pat / br;

        if (rx == px) {
            if (R < pat) {
                return pat = pat - br;
            }
            else {
                return pat = pat + br;
            }
        }
        else if (ry == py) {
            if (R < pat) {
                return pat = pat - 1;
            }
            else {
                return pat = pat + 1;
            }
        }

        // q 1 2 3 4
        else if (ry < py && rx < px)
        {
            if (rx < px - 1) return pat = pat - 1;
            else if (ry < (py - br)) return pat = pat - br;
            else return pat;
        }

        else if (ry > py && rx > px)
        {
            if (rx > px + 1) return pat = pat + 1;
            else if (ry > (py + br)) return pat = pat + br;
            else return pat;
        }

        else if (ry > py && rx < px)
        {
            if (rx < px - 1) return pat = pat - 1;
            else if (ry > (py + br)) return pat = pat + br;
            else return pat;
        }

        else if (ry < py && rx > px)
        {
            if (rx > px + 1) return pat = pat + 1;
            else if (ry < (py - br)) return pat = pat - br;
            else return pat;
        }

        // wait
    }
}

Compilation message (stderr)

coprobber.cpp: In function 'int nextMove(int)':
coprobber.cpp:133:1: warning: control reaches end of non-void function [-Wreturn-type]
  133 | }
      | ^

• Subtask 1: 16 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40