Submission #1105679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105679		elush	영역 (JOI16_ho_t4)	C++14	100 / 100	221 ms	41452 KiB

2016_ho_t4

#include <bits/stdc++.h>
#define chkmax(a, b) a = max(a, b)
#define all(v) v.begin(), v.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<vi> vvi;
typedef vector<pii> vii;

set<pii> points;
set<pii> squares;

void AddPoint(int x, int y) {
    points.insert({x, y});
    for (int i = -1; i < 1; i++) {
        for (int j = -1; j < 1; j++) {
            squares.insert({x + i, y + j});
//            if (x + i == -3 && y + j == 1) {
//                cout << "";
//            }
        }
    }
}

ll CountSquares(int n, int k, string route) {
    int x = 0, y = 0;
    AddPoint(x, y);
    for (char c : route) {
        if (c == 'N') x--;
        else if (c == 'E') y++;
        else if (c == 'S') x++;
        else y--;
        AddPoint(x, y);
    }
    if (!x && !y) {
        ll ans = 0;
        for (pii p : squares) {
            int c = 0;
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j < 2; j++) {
                    c += points.count({p.x + i, p.y + j});
                }
            }
            ans += c == 4;
        }
        return ans;
    }
    map<pii, vii> mp;
    for (pii p : squares) {
        ll startx = x ? (p.x % x + x) % x : p.x;
        ll starty = y ? (p.y % y + y) % y : p.y;
        ll mov = !x ? (p.y - starty) / y : (p.x - startx) / x;
        startx = p.x - mov * x, starty = p.y - mov * y;
        mp[{startx, starty}].push_back(p);
    }
    ll ans = 0;
    for (auto &[p, v] : mp) {
        vvi last(2, vi(2, -1));
        if (x < 0 || !x && y < 0) reverse(all(v));
        auto [bx, by] = v[0];
        vii ranges;
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < 2; j++) {
                for (int l = 0; l < 2; l++) {
                    if (points.count({v[i].x + j, v[i].y + l})) {
                        last[j][l] = i;
                    }
                }
            }
            ll min_i = min({last[0][0], last[0][1], last[1][0], last[1][1]});
            if (min_i == -1) continue;
            ll tim = x ? (v[i].x - v[min_i].x) / x : (v[i].y - v[min_i].y) / y;
            ll l = x ? (v[i].x - bx) / x : (v[i].y - by) / y;
            if (tim <= k) ranges.push_back({l, l + k - tim});
        }
        ll last_r = -1;
        for (auto [l, r] : ranges) {
            if (l <= last_r && r > last_r) {
                ans += r - last_r;
            } else if (l > last_r) {
                ans += r - l;
            }
            chkmax(last_r, r);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();
    int n, k;
    string route;
    cin >> n >> k >> route;
    cout << CountSquares(n, k, route);
}

Compilation message (stderr)

2016_ho_t4.cpp: In function 'll CountSquares(int, int, std::string)':
2016_ho_t4.cpp:60:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto &[p, v] : mp) {
      |                ^
2016_ho_t4.cpp:62:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         if (x < 0 || !x && y < 0) reverse(all(v));
      |                      ~~~^~~~~~~~
2016_ho_t4.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |         auto [bx, by] = v[0];
      |              ^
2016_ho_t4.cpp:65:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
2016_ho_t4.cpp:80:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |         for (auto [l, r] : ranges) {
      |                   ^

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