답안 #1098055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098055	2024-10-09T01:48:30 Z	Requiem	원 고르기 (APIO18_circle_selection)	C++17	100 / 100	922 ms	150172 KB

circle_selection

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define all(a) a.begin(),a.end()
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "circlesec"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Cho n đường tròn, đường tròn thứ i: có tâm (xi, yi) và bán kính ri.

Ta có 1 thuật toán:
- Tìm đường tròn có bán kính lớn nhất.
- Xóa đường tròn đó và những đường tròn giao với nó.
- Lặp lại bước 1 và 2 cho đến khi không còn đường tròn nào.

Ta gọi đường tròn i bị loại bởi đường tròn j nếu như khi đường tròn j bị loại ở bước 1 thì đường tròn i sẽ bị loại ở bước 2.

subtask 1: n <= 5000. O(N^2)
subtask 2: n <= 3e5. yi = 0, bài toán đưa về khoảng. Giả sử cho n đoạn [li, ri], ta sẽ xóa đoạn lớn nhất xong tìm những thằng
giao với đoạn đó và loại nó ra.

Subtask này đơn giản ta sweep qua các đoạn, với mỗi đoạn.
Ta lưu 3 cái set. Mỗi set sẽ sort theo 1 thông số li, ri, và radius.

Ta có nhận xét là những đoạn có l nằm trong [l, r] sẽ bị xóa xổ ở cả 3. Khi này, độ phức tạp chỉ là O(N log N) khi mỗi phần
tử chỉ được xóa 1 lần.

subtask 3: n <= 3e5, mỗi đường tròn chỉ giao với 1 đường tròn khác.
2 đường tròn giao nhau khi d(O1, O2) <= R1 + R2.

subtask 4: n <= 3e5, mỗi đường tròn có cùng bán kính.

**/

const int MAXN = 5e5 + 9;
struct Circle{
    int x, y, r, id;
    Circle(int _x = 0, int _y = 0, int _r = 0, int _id = 0): x(_x), y(_y), r(_r), id(_id) {}

    bool operator * (const Circle &other){
        return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y) <= (r + other.r) * (r + other.r);
    }
} circle[MAXN];

struct DSU{
    vector<int> lab;

    int small_to_large = 1;
    int path_compression = 1;

    DSU(int _sz = 0, int _small_to_large = 1, int _path_compression = 1){
        small_to_large = _small_to_large;
        path_compression = _path_compression;
        lab.resize(_sz + 1, -1);
    }

    int root(int u){
        if (path_compression)  return ((lab[u] < 0) ? u : lab[u] = root(lab[u]));
        return root(lab[u]);
    }

    void unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
//            cerr << "MERGE: " << u <<  ' ' << v << endl;
            if (lab[u] > lab[v] and small_to_large) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
        }
    }
};

struct gridding{
    vector<ii> grid;
    DSU remaining;

    void add(ii a){  //them 1 phan tu
        grid.pb(a);
    }

    void refine(){
        sort(grid.begin(), grid.end());
        remaining = DSU(grid.size() + 3, 0, 1);
    }

    int lb(ii x){
        return lower_bound(grid.begin(), grid.end(), x) - grid.begin() ;
    }

    int rb(ii x){
        int l = 0, r = grid.size() - 1, res = -1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if (grid[mid].fi < x.fi or (grid[mid].fi == x.fi and grid[mid].se > x.se)){
                res = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return res;
    }

    void toDelete(int l, int dir = 1){  //xoa 1 phan tu l.
        remaining.unite(l + dir, l);
    }
};

int n;

bool deleted[MAXN];
int answer[MAXN];
namespace subtask1{
    bool check(){
        return n <= 5000;
    }

    void solve(){
        memset(deleted, 0, sizeof(deleted));

        FOR(i, 1, n){
            int delId = 0, maxR = 0;

            FOR(j, 1, n){
                if (deleted[j]) continue;
                if (maximize(maxR, circle[j].r)) delId = j;
            }

//            cout << delId << endl;
            FOR(j, 1, n){
                if (!deleted[j] and circle[delId] * circle[j]) {
                    deleted[j] = true;
                    answer[j] = delId;
//                    cout << j << ' ';
                }
            }
//            cout << endl;
        }

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;

    }
}
namespace subtask2{
    bool check(){
        FOR(i,1 , n){
            if (circle[i].y != 0) return false;
        }
        return n <= 300000;
    }
    gridding sortX;
    gridding sortY;
    gridding sortR;

    void solve(){
        FOR(i, 1, n){
            int x = circle[i].x;
            circle[i].x = x - circle[i].r;
            circle[i].y = x + circle[i].r;
            sortX.add(ii(circle[i].x, i));
            sortY.add(ii(circle[i].y, i));
            sortR.add(ii(circle[i].r, i));
//            if (circle[i].r == 0) cout << i << endl;
        }
        vector<int> eraseList;
        sortX.refine();
        sortY.refine();
        sortR.add(ii(-inf, 0));
        sortR.refine();
        sort(all(sortR.grid), [&](const ii &a, const ii &b){
             return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        });
        int cur = n;
        while(cur > 0){
//        FOR(t, 0, 2){
            cur = sortR.remaining.root(cur);
            if (cur == 0) continue;
            int delId = sortR.grid[cur].se;
            int L = circle[delId].x;
            int R = circle[delId].y;

            int id1 = sortX.lb(ii(L, -inf));
            for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
                id1 = sortX.remaining.root(id1);
                if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;

                int idC = sortX.grid[id1].se;
                eraseList.pb(idC);
                sortX.toDelete(id1);

                int delId = sortY.lb(ii(circle[idC].y, circle[idC].id));
                sortY.toDelete(delId);
            }
            id1 = sortY.lb(ii(L, -inf));
            for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
                id1 = sortY.remaining.root(id1);
                if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
                int idC = sortY.grid[id1].se;

                eraseList.pb(idC);
                sortY.toDelete(id1);

                int delId = sortX.lb(ii(circle[idC].x, circle[idC].id));
                sortX.toDelete(delId);
            }

            for(auto p: eraseList){
                answer[p] = delId;
                int id = sortR.rb(ii(circle[p].r, circle[p].id));
                sortR.toDelete(id + 1, -1);
            }
            eraseList.clear();
        }
        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;
    }
}

namespace subtask3{
    bool check(){
        return true;
    }

    struct event{
        int x, id, type;
        event(int _x = 0, int _id = 0, int _type = 0): x(_x), id(_id), type(_type) {}
        //1: them
        //2: loai bo

        bool operator < (const event &other) const{
            if (x == other.x){
                if (type == other.type){
                    return id < other.id;
                }
                return type < other.type;
            }
            return x < other.x;
        }

    };

    struct cmp{
        bool operator() (const ii &a, const ii &b) const{
            return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        }
    };
    //moi duong tron chi giao voi toi da 1 duong tron khac.
    int other[MAXN];
    vector<event> events; //chua pair(x, i) la event.
    multiset<ii> listY;
    multiset<ii, cmp> sortR;
    void solve(){
        FOR(i, 1, n){
            sortR.insert(ii(circle[i].r, i));
            events.pb(event(circle[i].x - circle[i].r, i, 1));
            events.pb(event(circle[i].x - circle[i].r, i, 3));
            events.pb(event(circle[i].x, i, 3));
            events.pb(event(circle[i].x + circle[i].r, i, 3));
            events.pb(event(circle[i].x + circle[i].r + 1, i, 2));
        }
        sort(events.begin(),events.end());

        for(auto e: events){
            if (e.type == 1) {
                int addId = e.id;
                listY.insert(ii(circle[addId].y, addId));
            }
            else if (e.type == 3){
                int addId = e.id;
                auto it = listY.lower_bound(ii(circle[addId].y, addId));
                if (it != listY.end()){
                    auto nxt = next(it);
                    if (nxt != listY.end() and circle[addId] * circle[(*nxt).se]) {
                        other[addId] = (*nxt).se;
                        other[(*nxt).se] = addId;
                    }
                }

                if (it != listY.begin()){
                    auto prv = prev(it);
                    if (circle[addId] * circle[(*prv).se]) {
                        other[addId] = (*prv).se;
                        other[(*prv).se] = addId;
                    }
                }
            }

            else{
                int delId = e.id;
//                cout << "DEL: " << delId << endl;

                listY.erase(listY.find(ii(circle[delId].y, delId)));
            }
        }

        while(!sortR.empty()){
            auto it = *sortR.rbegin();

            int id = it.se;
            answer[id] = id;
//            cout << circle[id].id << endl;

            sortR.erase(sortR.find(it));

            if (other[id] != 0) {
                answer[other[id]] = id;
                ii tmp = ii(circle[other[id]].r, circle[other[id]].id);
                if (sortR.find(tmp) != sortR.end()) sortR.erase(sortR.find(tmp) );
            }
        }
//        FOR(i, 1, n){
//            cout << other[i] << ' ';
//        }
//        cout << endl;

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
    }
}

namespace subtask4{
    bool check(){
        FOR(i,1 , n){
            if (circle[i].r != circle[1].r) return false;
        }
        return true;
    }

    /**
    Idea cua sub nay la: ta se chia
    truc thanh cac o r * r.
    luc nay, ta chi can xet hinh trong co tam nam trong vung hinh vuong 5r * 5r.
    **/

    int maxR = 0;
    vector<int> listX;

    int getVal(vector<int> &listVal, int x){
        return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin();
    }


    struct cmpR{
        bool operator() (const ii &a, const ii &b) const{
            return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        }
    };

    multiset<ii, cmpR> sortR;  //chua ii(r, i)


    gridding grid[MAXN];  //chua ii(y, i)
    vector<int> toErase;
    void solve(){
        maxR = circle[1].r;
        FOR(i, 1, n){
            sortR.insert(ii(circle[i].r, circle[i].id));
        }

        FOR(i, 1, n){
            listX.pb(circle[i].x / maxR);
        }

        sort(listX.begin(), listX.end());
        listX.erase(unique(listX.begin(), listX.end()), listX.end());
//
        FOR(i, 1, n){
            int x = getVal(listX, circle[i].x / maxR);
            grid[x].add(ii(circle[i].y / maxR, i));
        }
        FOR(i, 0, MAXN - 1){
            grid[i].refine();
        }
//        FOR(i, 0, 2){
//            for(auto p: grid[i].grid){
//                cout << p.fi << ' ' << p.se << endl;
//            }
//            cout << endl;
//        }
//        cout << endl;
        while(!sortR.empty()){
            auto it = *sortR.rbegin();
            int id = it.se;
            answer[id] = id;
//            cout << id << endl;

            int discreteX = circle[id].x / maxR;
            int discreteY = circle[id].y / maxR;
//            cout << discreteX << ' ' << discreteY << endl;

            FOR(nx, discreteX - 2, discreteX + 2){
                int valX = getVal(listX, nx);
                toErase.clear();

                if (valX != listX.size() and listX[valX] == nx){

                    int id1 = grid[valX].lb(ii(discreteY - 2, -inf));
                    int cnt = 0;

//                    cout << "CHOSE: ";
                    for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
                        id1 = grid[valX].remaining.root(id1);
                        if (id1 >= grid[valX].grid.size()) continue;
                        int idC = grid[valX].grid[id1].se;
//                        cout << idC << ' ';
//                        cnt++;
                        if (circle[idC] * circle[id]) {
                            toErase.pb(idC);
                            answer[idC] = id;
                            grid[valX].toDelete(id1);
                        }
                        else id1++;
//                        if (cnt > n) break;
                    }
//                    cout << endl;
//
                    for(auto id: toErase){
                        ii t1 = ii(circle[id].r, circle[id].id);
                        if (sortR.find(t1) != sortR.end())
                            sortR.erase(sortR.find(t1));
                    }
                }
            }
        }

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;

    }
}

namespace subtask56{
    bool check(){
        return true;
    }

    /**
    Quy trình:
    Như subtask 4 nhưng ta sẽ chia maxR làm đôi mỗi khi curMaxR < maxR.
    Ta sẽ thêm 1 cái log vào kết quả.
    Độ phức tạp của ta có thể là O(N log N) + O(log 10^9) * O(scaling) + O(zi).
    **/

    Circle tmp[MAXN];  //sorted Circle.
    vector<gridding> grid;
    vector<int> listX;
    gridding sortR;
    int getVal(vector<int> &listVal, int x){
        return lower_bound(listVal.begin(), listVal.end(), x) - listVal.begin();
    }

    void rescaling(int maxSize){
        listX.clear();
        grid.clear();
        int cur = 0, lastX = -inf;
        FOR(i, 1, n){
            if (deleted[tmp[i].id]) continue;
            int id = tmp[i].id;
            int x1 = circle[id].x / maxSize;
            int y1 = circle[id].y / maxSize;
//            cout << circle[id].x << ' ' << circle[id].y << ' ' << circle[id].id <<endl;
            if (grid.size() == 0 or x1 != lastX) {
                if (!grid.empty()) grid.back().refine();
                grid.pb({});
            }

            grid.back().add(ii(y1, id));
            listX.pb(x1);
            lastX = x1;
            cur++;
        }
        listX.erase(unique(listX.begin(), listX.end()), listX.end());
//        cout << "SZ: " << listX.size() << ' ' << grid.size() << endl;
        if (!grid.empty()) grid.back().refine();
    }

    int maxRadius = 0;
    void solve(){
        FOR(i, 1, n){
            tmp[i] = circle[i];

            maximize(maxRadius, circle[i].r);
            sortR.add(ii(circle[i].r, circle[i].id));
        }
        sort(tmp + 1, tmp + 1 + n, [&](const Circle &a, const Circle &b){
             return (a.x == b.x) ? (a.y < b.y) : a.x < b.x;
        });

        sortR.add(ii(-inf, 0));
        sortR.refine();

        sort(all(sortR.grid), [&](const ii &a, const ii &b){
             return (a.fi == b.fi) ? (a.se > b.se) : (a.fi < b.fi);
        });

//
//        for(ii p: sortR.grid){
//            cout << p.fi << ' ' << p.se <<endl;
//        }
        int cur = n;
        vector<int> toErase;
        rescaling(maxRadius);
//        cout << listX.size() << ' ' << endl;
//        FOR(i, 0, (int) listX.size() - 1){
//            cout << listX[i] << endl;
//            for(ii id: grid[i].grid){
//                cout << id.fi << ' ' << id.se << endl;
//            }
//            cout << endl;
//        }

        while(cur > 0){
//        FOR(t, 0, 1){
            cur = sortR.remaining.root(cur);
            if (cur == 0) break;

            int delId = sortR.grid[cur].se;

            if (circle[delId].r < maxRadius / 2){
                rescaling(circle[delId].r);
                maxRadius = circle[delId].r;
            }



            int x = circle[delId].x / maxRadius;
            int y = circle[delId].y / maxRadius;
//            cout << x << ' ' << y << ' ' << delId  << endl;
//
            FOR(nx, x - 2, x + 2){
                int valX = getVal(listX, nx);
                if (valX < listX.size() and listX[valX] == nx){

                    int id = grid[valX].lb(ii(y - 2, -inf));
//                    cout << id << ' ' << grid[valX].grid[id].fi << endl;
                    for(;id < grid[valX].grid.size() and grid[valX].grid[id].fi <= y + 2;){
                        id = grid[valX].remaining.root(id);
//                        cout << id << endl;
                        if (id >= grid[valX].grid.size() or grid[valX].grid[id].fi > y + 2) break;
                        int idC = grid[valX].grid[id].se;
                        if (circle[idC] * circle[delId]){
//                            cout << "DELE: " <<idC << ' ' << delId << endl;
                            answer[idC] = delId;
                            deleted[idC] = true;
                            toErase.pb(idC);
                            grid[valX].toDelete(id);
                        }
                        else id++;
                    }

                    for(int idC: toErase){
                        int id = sortR.rb(ii(circle[idC].r, circle[idC].id));
                        sortR.toDelete(id + 1, -1);
                    }
//                    cout <<endl;
                    toErase.clear();
                }


            }
        }

        FOR(i, 1, n){
            cout << answer[i] << ' ';
        }
        cout << endl;
    }
}


void input(){
    cin >> n;
    FOR(i, 1, n){
        cin >> circle[i].x >> circle[i].y >> circle[i].r;
        circle[i].id = i;
    }

    if (subtask1::check()) return subtask1::solve();
    if (subtask2::check()) return subtask2::solve();
    if (subtask4::check()) return subtask4::solve();

    if (subtask56::check()) return subtask56::solve();

    if (subtask3::check()) return subtask3::solve();
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }

    input();

}
/**
Warning:
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

circle_selection.cpp: In function 'void subtask2::solve()':
circle_selection.cpp:200:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |             for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:202:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |                 if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:212:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  212 |             for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:214:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |                 if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:415:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  415 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:421:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  421 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:423:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  423 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:418:25: warning: unused variable 'cnt' [-Wunused-variable]
  418 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: In function 'void subtask56::solve()':
circle_selection.cpp:554:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  554 |                 if (valX < listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~
circle_selection.cpp:558:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  558 |                     for(;id < grid[valX].grid.size() and grid[valX].grid[id].fi <= y + 2;){
      |                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:561:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  561 |                         if (id >= grid[valX].grid.size() or grid[valX].grid[id].fi > y + 2) break;
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: At global scope:
circle_selection.cpp:608:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  608 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:612:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  612 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:613:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  613 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	79064 KB	Output is correct
2	Correct	42 ms	79184 KB	Output is correct
3	Correct	52 ms	79184 KB	Output is correct
4	Correct	46 ms	79164 KB	Output is correct
5	Correct	45 ms	79184 KB	Output is correct
6	Correct	43 ms	79184 KB	Output is correct
7	Correct	46 ms	79196 KB	Output is correct
8	Correct	44 ms	79188 KB	Output is correct
9	Correct	49 ms	79184 KB	Output is correct
10	Correct	45 ms	79072 KB	Output is correct
11	Correct	45 ms	79188 KB	Output is correct
12	Correct	45 ms	79188 KB	Output is correct
13	Correct	44 ms	79072 KB	Output is correct
14	Correct	43 ms	79188 KB	Output is correct
15	Correct	43 ms	79112 KB	Output is correct
16	Correct	46 ms	79136 KB	Output is correct
17	Correct	44 ms	79256 KB	Output is correct
18	Correct	45 ms	79188 KB	Output is correct
19	Correct	80 ms	79184 KB	Output is correct
20	Correct	90 ms	79188 KB	Output is correct
21	Correct	80 ms	79188 KB	Output is correct
22	Correct	99 ms	79388 KB	Output is correct
23	Correct	99 ms	79388 KB	Output is correct
24	Correct	97 ms	79188 KB	Output is correct
25	Correct	97 ms	79184 KB	Output is correct
26	Correct	100 ms	79184 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	371 ms	122092 KB	Output is correct
2	Correct	356 ms	116460 KB	Output is correct
3	Correct	345 ms	116972 KB	Output is correct
4	Correct	365 ms	120048 KB	Output is correct
5	Correct	337 ms	108552 KB	Output is correct
6	Correct	378 ms	108776 KB	Output is correct
7	Correct	382 ms	108900 KB	Output is correct
8	Correct	340 ms	108780 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	79016 KB	Output is correct
2	Correct	181 ms	89832 KB	Output is correct
3	Correct	473 ms	117332 KB	Output is correct
4	Correct	476 ms	117164 KB	Output is correct
5	Correct	449 ms	111784 KB	Output is correct
6	Correct	210 ms	96440 KB	Output is correct
7	Correct	124 ms	88776 KB	Output is correct
8	Correct	58 ms	81612 KB	Output is correct
9	Correct	477 ms	116140 KB	Output is correct
10	Correct	418 ms	112556 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	577 ms	129204 KB	Output is correct
2	Correct	560 ms	128440 KB	Output is correct
3	Correct	461 ms	128440 KB	Output is correct
4	Correct	568 ms	128820 KB	Output is correct
5	Correct	548 ms	129016 KB	Output is correct
6	Correct	424 ms	127412 KB	Output is correct

Subtask #5

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	79064 KB	Output is correct
2	Correct	42 ms	79184 KB	Output is correct
3	Correct	52 ms	79184 KB	Output is correct
4	Correct	46 ms	79164 KB	Output is correct
5	Correct	45 ms	79184 KB	Output is correct
6	Correct	43 ms	79184 KB	Output is correct
7	Correct	46 ms	79196 KB	Output is correct
8	Correct	44 ms	79188 KB	Output is correct
9	Correct	49 ms	79184 KB	Output is correct
10	Correct	45 ms	79072 KB	Output is correct
11	Correct	45 ms	79188 KB	Output is correct
12	Correct	45 ms	79188 KB	Output is correct
13	Correct	44 ms	79072 KB	Output is correct
14	Correct	43 ms	79188 KB	Output is correct
15	Correct	43 ms	79112 KB	Output is correct
16	Correct	46 ms	79136 KB	Output is correct
17	Correct	44 ms	79256 KB	Output is correct
18	Correct	45 ms	79188 KB	Output is correct
19	Correct	80 ms	79184 KB	Output is correct
20	Correct	90 ms	79188 KB	Output is correct
21	Correct	80 ms	79188 KB	Output is correct
22	Correct	99 ms	79388 KB	Output is correct
23	Correct	99 ms	79388 KB	Output is correct
24	Correct	97 ms	79188 KB	Output is correct
25	Correct	97 ms	79184 KB	Output is correct
26	Correct	100 ms	79184 KB	Output is correct
27	Correct	46 ms	79820 KB	Output is correct
28	Correct	47 ms	79820 KB	Output is correct
29	Correct	47 ms	79820 KB	Output is correct
30	Correct	51 ms	80096 KB	Output is correct
31	Correct	51 ms	80332 KB	Output is correct
32	Correct	51 ms	80244 KB	Output is correct
33	Correct	109 ms	90812 KB	Output is correct
34	Correct	110 ms	90812 KB	Output is correct
35	Correct	116 ms	89832 KB	Output is correct
36	Correct	168 ms	93216 KB	Output is correct
37	Correct	180 ms	92864 KB	Output is correct
38	Correct	174 ms	92128 KB	Output is correct
39	Correct	308 ms	88220 KB	Output is correct
40	Correct	305 ms	88224 KB	Output is correct
41	Correct	295 ms	88360 KB	Output is correct
42	Correct	183 ms	99852 KB	Output is correct
43	Correct	219 ms	100816 KB	Output is correct
44	Correct	220 ms	100692 KB	Output is correct
45	Correct	217 ms	100560 KB	Output is correct
46	Correct	215 ms	100552 KB	Output is correct
47	Correct	211 ms	100864 KB	Output is correct
48	Correct	215 ms	100560 KB	Output is correct
49	Correct	214 ms	100816 KB	Output is correct
50	Correct	221 ms	100756 KB	Output is correct

Subtask #6

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	79064 KB	Output is correct
2	Correct	42 ms	79184 KB	Output is correct
3	Correct	52 ms	79184 KB	Output is correct
4	Correct	46 ms	79164 KB	Output is correct
5	Correct	45 ms	79184 KB	Output is correct
6	Correct	43 ms	79184 KB	Output is correct
7	Correct	46 ms	79196 KB	Output is correct
8	Correct	44 ms	79188 KB	Output is correct
9	Correct	49 ms	79184 KB	Output is correct
10	Correct	45 ms	79072 KB	Output is correct
11	Correct	45 ms	79188 KB	Output is correct
12	Correct	45 ms	79188 KB	Output is correct
13	Correct	44 ms	79072 KB	Output is correct
14	Correct	43 ms	79188 KB	Output is correct
15	Correct	43 ms	79112 KB	Output is correct
16	Correct	46 ms	79136 KB	Output is correct
17	Correct	44 ms	79256 KB	Output is correct
18	Correct	45 ms	79188 KB	Output is correct
19	Correct	80 ms	79184 KB	Output is correct
20	Correct	90 ms	79188 KB	Output is correct
21	Correct	80 ms	79188 KB	Output is correct
22	Correct	99 ms	79388 KB	Output is correct
23	Correct	99 ms	79388 KB	Output is correct
24	Correct	97 ms	79188 KB	Output is correct
25	Correct	97 ms	79184 KB	Output is correct
26	Correct	100 ms	79184 KB	Output is correct
27	Correct	371 ms	122092 KB	Output is correct
28	Correct	356 ms	116460 KB	Output is correct
29	Correct	345 ms	116972 KB	Output is correct
30	Correct	365 ms	120048 KB	Output is correct
31	Correct	337 ms	108552 KB	Output is correct
32	Correct	378 ms	108776 KB	Output is correct
33	Correct	382 ms	108900 KB	Output is correct
34	Correct	340 ms	108780 KB	Output is correct
35	Correct	45 ms	79016 KB	Output is correct
36	Correct	181 ms	89832 KB	Output is correct
37	Correct	473 ms	117332 KB	Output is correct
38	Correct	476 ms	117164 KB	Output is correct
39	Correct	449 ms	111784 KB	Output is correct
40	Correct	210 ms	96440 KB	Output is correct
41	Correct	124 ms	88776 KB	Output is correct
42	Correct	58 ms	81612 KB	Output is correct
43	Correct	477 ms	116140 KB	Output is correct
44	Correct	418 ms	112556 KB	Output is correct
45	Correct	577 ms	129204 KB	Output is correct
46	Correct	560 ms	128440 KB	Output is correct
47	Correct	461 ms	128440 KB	Output is correct
48	Correct	568 ms	128820 KB	Output is correct
49	Correct	548 ms	129016 KB	Output is correct
50	Correct	424 ms	127412 KB	Output is correct
51	Correct	46 ms	79820 KB	Output is correct
52	Correct	47 ms	79820 KB	Output is correct
53	Correct	47 ms	79820 KB	Output is correct
54	Correct	51 ms	80096 KB	Output is correct
55	Correct	51 ms	80332 KB	Output is correct
56	Correct	51 ms	80244 KB	Output is correct
57	Correct	109 ms	90812 KB	Output is correct
58	Correct	110 ms	90812 KB	Output is correct
59	Correct	116 ms	89832 KB	Output is correct
60	Correct	168 ms	93216 KB	Output is correct
61	Correct	180 ms	92864 KB	Output is correct
62	Correct	174 ms	92128 KB	Output is correct
63	Correct	308 ms	88220 KB	Output is correct
64	Correct	305 ms	88224 KB	Output is correct
65	Correct	295 ms	88360 KB	Output is correct
66	Correct	183 ms	99852 KB	Output is correct
67	Correct	219 ms	100816 KB	Output is correct
68	Correct	220 ms	100692 KB	Output is correct
69	Correct	217 ms	100560 KB	Output is correct
70	Correct	215 ms	100552 KB	Output is correct
71	Correct	211 ms	100864 KB	Output is correct
72	Correct	215 ms	100560 KB	Output is correct
73	Correct	214 ms	100816 KB	Output is correct
74	Correct	221 ms	100756 KB	Output is correct
75	Correct	283 ms	116140 KB	Output is correct
76	Correct	275 ms	112612 KB	Output is correct
77	Correct	281 ms	117676 KB	Output is correct
78	Correct	279 ms	117416 KB	Output is correct
79	Correct	305 ms	110064 KB	Output is correct
80	Correct	283 ms	117592 KB	Output is correct
81	Correct	466 ms	117160 KB	Output is correct
82	Correct	483 ms	121420 KB	Output is correct
83	Correct	496 ms	121516 KB	Output is correct
84	Correct	461 ms	116708 KB	Output is correct
85	Correct	485 ms	117672 KB	Output is correct
86	Correct	503 ms	122028 KB	Output is correct
87	Correct	481 ms	113584 KB	Output is correct
88	Correct	907 ms	110212 KB	Output is correct
89	Correct	880 ms	110156 KB	Output is correct
90	Correct	916 ms	110180 KB	Output is correct
91	Correct	888 ms	110156 KB	Output is correct
92	Correct	922 ms	110248 KB	Output is correct
93	Correct	506 ms	149928 KB	Output is correct
94	Correct	361 ms	108716 KB	Output is correct
95	Correct	588 ms	149916 KB	Output is correct
96	Correct	504 ms	149660 KB	Output is correct
97	Correct	468 ms	109740 KB	Output is correct
98	Correct	399 ms	127404 KB	Output is correct
99	Correct	500 ms	150172 KB	Output is correct
100	Correct	477 ms	149932 KB	Output is correct
101	Correct	437 ms	116140 KB	Output is correct
102	Correct	529 ms	149712 KB	Output is correct
103	Correct	434 ms	110764 KB	Output is correct
104	Correct	565 ms	149916 KB	Output is correct
105	Correct	488 ms	126648 KB	Output is correct
106	Correct	597 ms	129208 KB	Output is correct
107	Correct	606 ms	129204 KB	Output is correct
108	Correct	612 ms	129208 KB	Output is correct
109	Correct	592 ms	129204 KB	Output is correct
110	Correct	606 ms	129212 KB	Output is correct
111	Correct	596 ms	129044 KB	Output is correct
112	Correct	630 ms	129024 KB	Output is correct
113	Correct	617 ms	129068 KB	Output is correct
114	Correct	620 ms	129016 KB	Output is correct
115	Correct	623 ms	129208 KB	Output is correct
116	Correct	590 ms	129212 KB	Output is correct