Submission #412479

#	Time	Username	Problem	Language	Result	Execution time	Memory
412479		tatyam	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	2098 ms	1048580 KiB

hexagon

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

constexpr uint mod = 1'000'000'007;
struct Modint{
    uint num = 0;
    Modint(){}
    template<class T> Modint(T x): num(x % mod){}
    operator int() const { return num; }
    void operator+=(Modint x){
        num += x.num;
        if(num >= mod) num -= mod;
    }
    void operator-=(Modint x){
        if(num < x.num) num += mod;
        num -= x.num;
    }
    Modint operator+(Modint x) const {
        Modint ans = *this;
        ans += x;
        return ans;
    }
    Modint operator-(Modint x) const {
        Modint ans = *this;
        ans -= x;
        return ans;
    }
    Modint operator*(Modint x) const {
        return uint((uint64_t)num * x.num % mod);
    }
};

const int dx[6] = {0, 1, 1, 0, -1, -1}, dy[6] = {1, 1, 0, -1, -1, 0};
int draw_territory2(int N, int A, int B, vector<int> D, vector<int> L){
    assert(L[0] == L[1] && L[1] == L[2]);
    Modint n = L[0];
    return (n * Modint(2 * 333333336) * Modint(B) + Modint(A)) * Modint(uint64_t(2 + n) * (1 + n) / 2);
}
int draw_territory5(int N, Modint A, Modint B, vector<int> D, vector<int> L){
    const Modint sqrt3 = 82062379;
    const Modint dx[6] = {0, sqrt3, sqrt3, 0, mod - sqrt3, mod - sqrt3}, dy[6] = {1, (mod + 1) / 2, mod - (mod + 1) / 2, -1, mod - (mod + 1) / 2, (mod + 1) / 2};
    Modint ans = 0;
    Modint x = 0, y = 0;
    for(int i = 0; i < N; i++){
        
    }
    return ans * Modint(A);
}
int draw_territory6(int N, Modint A, Modint B, vector<int> D, vector<int> L){
    vector<pair<int, int>> path, inside, outside;
    int x = 0, y = 0;
    for(int i = 0; i < N; i++){
        const int d = --D[i], d1 = (d + 5) % 6, d2 = (d + 1) % 6;
        while(L[i]--){
            inside.emplace_back(x + dx[d1], y + dy[d1]);
            outside.emplace_back(x + dx[d2], y + dy[d2]);
            path.emplace_back(x += dx[d], y += dy[d]);
        }
    }
    unordered_set point(path.begin(), path.end(), 1000000, [](pair<int, int> a){ return (uint64_t)a.first << 32 ^ a.second; });
    auto rem = [&](auto& a){
        a.erase(remove_if(a.begin(), a.end(), [&](auto x){ return !point.insert(x).second; }), a.end());
    };
    rem(inside);
    rem(outside);
    point.insert(inside.begin(), inside.end());
    point.insert(outside.begin(), outside.end());
    auto search1 = [&, i = 0]() mutable -> bool {
        if(i == inside.size()) return 1;
        auto [x, y] = inside[i];
        for(int d = 0; d < 6; d++){
            const int x2 = x + dx[d], y2 = y + dy[d];
            if(point.emplace(x2, y2).second) inside.emplace_back(x2, y2);
        }
        i++;
        return 0;
    };
    auto search2 = [&, i = 0]() mutable -> bool {
        if(i == outside.size()) return 1;
        auto [x, y] = outside[i];
        for(int d = 0; d < 6; d++){
            const int x2 = x + dx[d], y2 = y + dy[d];
            if(point.emplace(x2, y2).second) outside.emplace_back(x2, y2);
        }
        i++;
        return 0;
    };
    while(1){
        if(search1()) break;
        if(search2()){
            swap(inside, outside);
            break;
        }
    }
    for(auto i : outside) point.erase(i);
    Modint ans = 0;
    queue<tuple<int, int, int>> q;
    q.emplace(0, 0, 0);
    point.erase({0, 0});
    while(q.size()){
        auto [x, y, c] = q.front();
        ans += (uint64_t) B * c + A;
        q.pop();
        for(int d = 0; d < 6; d++){
            const int x2 = x + dx[d], y2 = y + dy[d];
            if(point.count({x2, y2})){
                q.emplace(x2, y2, c + 1);
                point.erase({x2, y2});
            }
        }
    }
    return ans;
}
int draw_territory(int N, int A, int B, vector<int> D, vector<int> L){
    if(N == 3) return draw_territory2(N, A, B, D, L);
    return draw_territory6(N, A, B, D, L);
}

Compilation message (stderr)

hexagon.cpp: In function 'int draw_territory5(int, Modint, Modint, std::vector<int>, std::vector<int>)':
hexagon.cpp:42:18: warning: unused variable 'dx' [-Wunused-variable]
   42 |     const Modint dx[6] = {0, sqrt3, sqrt3, 0, mod - sqrt3, mod - sqrt3}, dy[6] = {1, (mod + 1) / 2, mod - (mod + 1) / 2, -1, mod - (mod + 1) / 2, (mod + 1) / 2};
      |                  ^~
hexagon.cpp:42:74: warning: unused variable 'dy' [-Wunused-variable]
   42 |     const Modint dx[6] = {0, sqrt3, sqrt3, 0, mod - sqrt3, mod - sqrt3}, dy[6] = {1, (mod + 1) / 2, mod - (mod + 1) / 2, -1, mod - (mod + 1) / 2, (mod + 1) / 2};
      |                                                                          ^~
hexagon.cpp:44:12: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   44 |     Modint x = 0, y = 0;
      |            ^
hexagon.cpp:44:19: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   44 |     Modint x = 0, y = 0;
      |                   ^
hexagon.cpp: In lambda function:
hexagon.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         if(i == inside.size()) return 1;
      |            ~~^~~~~~~~~~~~~~~~
hexagon.cpp: In lambda function:
hexagon.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if(i == outside.size()) return 1;
      |            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16