oj.uz

Submission #594118

# Submission time Handle Problem Language Result Execution time Memory
594118 2022-07-12T06:36:16 Z 박상훈(#8431) None (JOI16_ho_t4) C++17
28 / 100
 2 ms 468 KB 
#include <bits/stdc++.h>
#define int long long

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){
        if (cc['E'] == 0) swap(cc['E'], cc['W']);
        else swap(cc['S'], cc['N']);
        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;
            }

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

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

mt19937 seed(129438);
uniform_int_distribution<int> rng(0, 2147483647);
int getrand(int l, int r){return rng(seed)%(r-l+1) + l;}

signed main(){
    scanf("%lld %lld", &n, &k);
    scanf("%s", s+1);
    /*for (int i=1;i<=n;i++){
        char t[10] = "xESWN";
        s[i] = t[getrand(1, 4)];
        printf("%c", s[i]);
    }
    printf("\n");*/

    init();

    solve();

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

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Incorrect 2 ms 468 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 292 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 0 ms 212 KB Output is correct
44 Correct 1 ms 292 KB Output is correct
45 Correct 0 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Incorrect 2 ms 468 KB Output isn't correct
28 Halted 0 ms 0 KB -