Submission #873180

#	Time	Username	Problem	Language	Result	Execution time	Memory
873180		hgmhc	영역 (JOI16_ho_t4)	C++17	0 / 100	1 ms	2520 KiB

2016_ho_t4

// 일단 내보기
// 그 뭐냐 예제 4에서 뒷쪽에 의해 정사각형이 색칠되는게 제대로 고려 안 됨
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long; using vi = vector<int>;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

#pragma region Geometry
using P = complex<ll>; using ld = long double; using Poly = vector<P>;
const ld PI = acos(-1.0L), TAU = 2*PI;
#define X real()
#define Y imag()
inline ll dot(P u, P v) { return (conj(u)*v).X; }
inline ll cross(P u, P v) { return (conj(u)*v).Y; }
inline ll norm(P u) { return dot(u,u); }
inline int ccw(P a, P b, P c) {
    auto v = cross(b-a,c-b);
    if (v < 0) return -1;
    else if (v > 0) return 1;
    return 0;
}
P operator * (const P &lhs, const ll &rhs) { return {lhs.X * rhs, lhs.Y * rhs}; }
inline ld abs(P u) {return sqrt(ld(norm(u)));}
istream &operator >> (istream &is, P &p) {ll x, y; is >> x >> y; p = {x,y}; return is;}
namespace std { bool operator < (const P &u, const P &v) {return u.X == v.X ? u.Y < v.Y : u.X < v.X;} }
#pragma endregion

constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); }
constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); }

const int N = 1e5+3;
int n, k;
P v[N], p[N];
set<P> s;
map<P,vector<ll>> m;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    rep(i,1,n) {
        char c; cin >> c;
        if (c=='W') v[i]={-1,0};
        if (c=='S') v[i]={0,+1};
        if (c=='N') v[i]={0,-1};
        if (c=='E') v[i]={+1,0};
        p[i] = v[i]+p[i-1];
    }
    ll d = 0;
    auto nor = [&](P x) {
        d=0;
        if (p[n].X) d = floor(x.X,p[n].X);
        else if (p[n].Y) d = floor(x.Y,p[n].Y);
        return x-p[n]*d;
    };
    rep(i,0,n) {
        P t = nor(p[i]);
        m[t].push_back(d);
    }
    ll ans = 0;
    for (auto &[k,v] : m) sort(all(v));
    map<P,bool> done;
    rep(i,0,n) {
        for (auto e : {p[i],p[i]+P{-1,0},p[i]+P{0,-1},p[i]+P{-1,-1}}) {
            ll x = e.X, y = e.Y, z = 0;
            vector<ll> vec;
            
            if (m.count(nor({x,y}))) {
                vec = m[nor({x,y})];
                if (!binary_search(all(vec),d)) {
                    auto it = upper_bound(all(vec),d);
                    if (it != begin(vec))
                        Mup(z, 0LL+(d-*prev(it)));
                    else continue;
                }
            } else continue;
            
            if (m.count(nor({x+1,y}))) {
                vec = m[nor({x+1,y})];
                if (!binary_search(all(vec),d)) {
                    auto it = upper_bound(all(vec),d);
                    if (it != begin(vec))
                        Mup(z, 0LL+(d-*prev(it)));
                    else continue;
                }
            } else continue;
            
            if (m.count(nor({x,y+1}))) {
                vec = m[nor({x,y+1})];
                if (!binary_search(all(vec),d)) {
                    auto it = upper_bound(all(vec),d);
                    if (it != begin(vec))
                        Mup(z, 0LL+(d-*prev(it)));
                    else continue;
                }
            } else continue;
            
            if (m.count(nor({x+1,y+1}))) {
                vec = m[nor({x+1,y+1})];
                if (!binary_search(all(vec),d)) {
                    auto it = upper_bound(all(vec),d);
                    if (it != begin(vec))
                        Mup(z, 0LL+(d-*prev(it)));
                    else continue;
                }
            } else continue;
            
            if (done[nor({x,y})]) continue;
            done[nor({x,y})] = true;
            
            // cout << e << ' ' << nor(e) << ' ' << z << endl;
            ans += max(0LL,k-z);
        }
    }
    cout << ans;
}

Compilation message (stderr)

2016_ho_t4.cpp:15: warning: ignoring '#pragma region Geometry' [-Wunknown-pragmas]
   15 | #pragma region Geometry
      | 
2016_ho_t4.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 62