Submission #846325

#	Time	Username	Problem	Language	Result	Execution time	Memory
846325		vjudge1	ČVENK (COI15_cvenk)	C++17	0 / 100	3048 ms	43524 KiB

cvenk

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
//#define int long long

const int MAXN = 505;

#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    #define OPEN freopen(".in", "r", stdin); \
                 freopen(".out", "w", stdout);
#else
    #define OPEN void(23);
#endif

int cnts[MAXN][MAXN];
int ans[MAXN][MAXN];

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int go[] = {2, 3, 0, 1};

bool check(int a, int b, int c, int d)
{
    if(0 > min(a, b) || max(a, b) >= MAXN) return false;

    return (a & b) == 0;
}

void solve()
{
    int n; cin >> n;
    queue <tuple <int, int, int, int>> q;
    for(int i = 1; i <= n; i++)
    {
        int a, b; cin >> a >> b;
        q.emplace(a, b, 0, -1);
    }

    while(!q.empty())
    {
        auto [x, y, t, yon] = q.front();
        q.pop();
        cnts[x][y]++;
        ans[x][y] += t;

        for(int i = 0; i < 4; i++)
        {
            int _x = x + dx[i], _y = y + dy[i];
            if(check(_x, _y, x, y) && i != yon) q.emplace(_x, _y, t +1, go[i]);
        }
    }

    int cev = 1e9;
    for(int i = 0; i < MAXN; i++)
    {
        for(int j = 0; j < MAXN; j++)
        {
            if(cnts[i][j] == n)
                cev = min(cev, ans[i][j]);
        }
    }

    cout << cev;

    return;
}

int32_t main()
{
    OPEN;

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1; //cin >> t;
    while(t--)
    {
        solve();
    }
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40