oj.uz

답안 #594105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594105 2022-07-12T06:02:29 Z 박상훈(#8431) 영역 (JOI16_ho_t4) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int n, k, dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1}, cc[1234];
char s[100100];
map<pair<ll, ll>, vector<pair<ll, ll>>> M;
ll a, b, d, ans;

pair<ll, ll> _convert(ll x, ll y){
    return {a*x+b*y, x/(a/d)%d};
}

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}

ll fx = 0, fy = 0;
void simulate(bool flag){

    if (flag) M[_convert(0, 0)].emplace_back(fx, fx+(ll)k*a);

    for (int i=1;i<=n;i++){
        fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];

        if (flag){
            auto p = _convert(fx, fy);
            M[p].emplace_back(fx, fx + (ll)k*a);
        }
    }
}

void compress(vector<pair<ll, ll>> &V){
    vector<pair<ll, ll>> ret;
    sort(V.begin(), V.end());

    for (auto &[s, e]:V){
        if (ret.empty()) {ret.emplace_back(s, e); continue;}

        if (ret.back().second>=s) ret.back().second = e;
        else ret.emplace_back(s, e);
    }
    swap(V, ret);
}

void init(){
    cc['E'] = 0, cc['S'] = 1, cc['W'] = 2, cc['N'] = 3;
    simulate(0);
    if (fx==0 && fy==0) {fx = 1; k = 1;}

    else if (fx==0){
        cc['E'] = 3, cc['N'] = 0;
        cc['S'] = 2, cc['W'] = 1;
        fx = 0, fy = 0;
        simulate(0);
        assert(fx);
    }

    d = myabs(__gcd(fx, fy));
    a = -fy, b = fx;
    fx = 0, fy = 0;

    //printf(" a = %lld, b = %lld, d = %lld\n", a, b, d);

    simulate(1);
    for (auto &[p, V]:M) compress(V);

    //printf("Init ok\n");
}

void get_event(vector<pair<ll, int>> &Event, vector<pair<ll, ll>> &V, int ofs){
    for (auto &[s, e]:V){
        Event.emplace_back(s+ofs, 1);
        Event.emplace_back(e+ofs, -1);
    }
}

bool valid(ll x, ll y){
    if (M.find(_convert(x, y+1))==M.end()) return 0;
    if (M.find(_convert(x+1, y))==M.end()) return 0;
    if (M.find(_convert(x+1, y+1))==M.end()) return 0;
    return 1;
}

void solve(){
    for (auto &[p, V]:M){
        ll x = V[0].first;
        ll y = (p.first - x*a) / b;

        if (!valid(x, y)) continue;

        vector<pair<ll, int>> Event;
        get_event(Event, V, 0);
        get_event(Event, M[_convert(x, y+1)], 0);
        get_event(Event, M[_convert(x+1, y)], -1);
        get_event(Event, M[_convert(x+1, y+1)], -1);

        sort(Event.begin(), Event.end());

        int cnt = 0;
        for (int i=0;i<(int)Event.size();){
            int r = i;
            for (;r<(int)Event.size();r++){
                if (Event[i].first!=Event[r].first) break;
                cnt += Event[r].second;
            }

            if (cnt==4){
                assert(r<(int)Event.size());
                ans += (Event[r].first - Event[i].first) / a;
            }

            assert(i<r);
            i = r;
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    scanf("%s", s+1);

    init();

    solve();

    printf("%lld\n", ans);
    return 0;
}

Compilation message

2016_ho_t4.cpp: In function 'void simulate(bool)':
2016_ho_t4.cpp:25:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |         fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];
      |                     ~~~^
2016_ho_t4.cpp:25:44: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |         fx += dx[cc[s[i]]], fy += dy[cc[s[i]]];
      |                                         ~~~^
2016_ho_t4.cpp: In function 'int main()':
2016_ho_t4.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
2016_ho_t4.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%s", s+1);
      |     ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -