답안 #45404 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45404	2018-04-13T08:19:00 Z	grumpy_gordon	Park (BOI16_park)	C++17	100 / 100	832 ms	55264 KB

park

/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef unsigned int uint;

ll sqr(ll x){
    return x * x;
}

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1227);

mt19937_64 rndll(12365);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 7;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

void setmin(ll &x, ll y){
    x = min(x, y);
}

void setmax(ll &x, ll y){
    x = max(x, y);
}

int gcd(int a, int b){
    return a ? gcd(b % a, a) : b;
}

const ll llinf = 2e18 + 100;

const double eps = 1e-9;

const int maxn = 1e5 + 100, maxw = 1e7 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;

int n, w, h;

pair<int, int> a[maxn];

int rad[maxn];

pair<ll, ll> getw(int i, int j){
    if (i < 0 && j < 0)
        return make_pair(inf, inf);
    if (i < 0)
        swap(i, j);
    if (j == -1)
        return make_pair(sqr(a[i].second), rad[i]);
    if (j == -2)
        return make_pair(sqr(w - a[i].first), rad[i]);
    if (j == -3)
        return make_pair(sqr(h - a[i].second), rad[i]);
    if (j == -4)
        return make_pair(sqr(a[i].first), rad[i]);
    return make_pair(sqr(a[i].first - a[j].first) + sqr(a[i].second - a[j].second), rad[i] + rad[j]);
}

void precalc(){

}

int p[maxn], rnk[maxn];

int get(int x){
    return x == p[x] ? x : p[x] = get(p[x]);
}

void uni(int x, int y){
    x = get(x);
    y = get(y);
    if (x == y)
        return;
    if (rnk[x] < rnk[y])
        swap(x, y);
    p[y] = x;
    if (rnk[x] == rnk[y])
        rnk[x]++;
}

int ae[4][4];

void add(int x, int y){
    ae[x][y] = 1;
    ae[y][x] = 1;
}

string calc(int r, int t){
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            ae[i][j] = 0;
    if (get(0) == get(1))
        add(0, 3), add(1, 3), add(2, 3);
    if (get(0) == get(2))
        add(0, 2), add(0, 3), add(1, 2), add(1, 3);
    if (get(0) == get(3))
        add(0, 1), add(0, 2), add(0, 3);
    if (get(1) == get(2))
        add(0, 2), add(1, 2), add(3, 2);
    if (get(1) == get(3))
        add(0, 2), add(0, 1), add(3, 2), add(3, 1);
    if (get(2) == get(3))
        add(0, 1), add(2, 1), add(3, 1);
    string ret;
    for (int i = 0; i < 4; i++)
    if (!ae[t][i])
        ret.push_back(49 + i);
    return ret;
}

pair<pair<int, int>, int> que[maxn];

vector<pair<int, int> > g[maxn];

string ans[maxn];

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("gymnasts.in");
    //ofstream cout("gymnasts.out");
    //freopen("sort.in", "r", stdin);
    //freopen("sort.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int zap;
    cin >> n >> zap >> w >> h;
    for (int i = 0; i < n; i++)
        cin >> a[i].first >> a[i].second >> rad[i];
    precalc();
    for (int i = 0; i < zap; i++)
        cin >> que[i].first.first >> que[i].first.second, que[i].first.second--, que[i].second = i;
    sort(que, que + zap);
    for (int i = 0; i < n + 4; i++)
        p[i] = i, rnk[i] = 0;
    for (int i = 0; i < n + 4; i++)
    for (int j = 0; j < n + 4; j++){
        pair<ll, ll> x = getw(i - 4, j - 4);
        int L = -1, R = zap;
        while (R - L > 1){
            int m = (L + R) / 2;
            if (x != make_pair((ll)inf, (ll)inf) && x.first < sqr(x.second + 2 * que[m].first.first))
                R = m;
            else
                L = m;
        }
        if (R < zap)
            g[R].push_back(make_pair(i, j));
    }
    for (int i = 0; i < zap; i++){
        for (auto j : g[i])
            uni(j.first, j.second);
        ans[que[i].second] = calc(que[i].first.first, que[i].first.second);
    }
    for (int i = 0; i < zap; i++)
        cout << ans[i] << '\n';
}

Subtask #1
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	6008 KB	Output is correct
2	Correct	65 ms	6172 KB	Output is correct
3	Correct	50 ms	6172 KB	Output is correct
4	Correct	39 ms	6172 KB	Output is correct
5	Correct	44 ms	6172 KB	Output is correct
6	Correct	40 ms	6260 KB	Output is correct
7	Correct	127 ms	39200 KB	Output is correct
8	Correct	64 ms	39200 KB	Output is correct
9	Correct	6 ms	39200 KB	Output is correct
10	Correct	7 ms	39200 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	39200 KB	Output is correct
2	Correct	63 ms	39200 KB	Output is correct
3	Correct	86 ms	39200 KB	Output is correct
4	Correct	97 ms	39200 KB	Output is correct
5	Correct	61 ms	39200 KB	Output is correct
6	Correct	95 ms	39200 KB	Output is correct
7	Correct	73 ms	39200 KB	Output is correct
8	Correct	69 ms	39200 KB	Output is correct

Subtask #3
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	6008 KB	Output is correct
2	Correct	65 ms	6172 KB	Output is correct
3	Correct	50 ms	6172 KB	Output is correct
4	Correct	39 ms	6172 KB	Output is correct
5	Correct	44 ms	6172 KB	Output is correct
6	Correct	40 ms	6260 KB	Output is correct
7	Correct	127 ms	39200 KB	Output is correct
8	Correct	64 ms	39200 KB	Output is correct
9	Correct	6 ms	39200 KB	Output is correct
10	Correct	7 ms	39200 KB	Output is correct
11	Correct	72 ms	39200 KB	Output is correct
12	Correct	63 ms	39200 KB	Output is correct
13	Correct	86 ms	39200 KB	Output is correct
14	Correct	97 ms	39200 KB	Output is correct
15	Correct	61 ms	39200 KB	Output is correct
16	Correct	95 ms	39200 KB	Output is correct
17	Correct	73 ms	39200 KB	Output is correct
18	Correct	69 ms	39200 KB	Output is correct
19	Correct	648 ms	39200 KB	Output is correct
20	Correct	631 ms	39200 KB	Output is correct
21	Correct	637 ms	39200 KB	Output is correct
22	Correct	626 ms	39200 KB	Output is correct
23	Correct	630 ms	39200 KB	Output is correct
24	Correct	832 ms	55264 KB	Output is correct

답안 #45404

Compilation message

Subtask #1 27.0 / 27.0

Subtask #2 31.0 / 31.0

Subtask #3 42.0 / 42.0

Subtask #1
27.0 / 27.0

Subtask #2
31.0 / 31.0

Subtask #3
42.0 / 42.0