oj.uz

Submission #594110

# Submission time Handle Problem Language Result Execution time Memory
594110 2022-07-12T06:22:46 Z 박상훈(#8431) None (JOI16_ho_t4) C++17
0 / 100
 1 ms 468 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;

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

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


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

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

    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*b);
        }

        //if (flag)printf(" %lld %lld\n", fx, fy);
    }
}

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);
    }

    if (fx<0){
        swap(cc['E'], cc['W']);
        fx = 0, fy = 0;
        simulate(0);
        assert(fx>0);
    }

    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){
        //printf(" %lld: %d\n", p.first, (int)V.size());
        ll x = V[0].first;
        ll y = (p.first - x*a) / b;

        if (!valid(x, y)) continue;
        //printf("YES: %lld %lld\n", x, y);

        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());
        //for (auto [t, i]:Event) printf("  %lld -> %d\n", t, i);

        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) / b;
            }

            assert(i<r);
            i = r;
        }
        //printf(" ok\n");
    }
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -