답안 #1097928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097928	2024-10-08T16:03:56 Z	Requiem	원 고르기 (APIO18_circle_selection)	C++17	57 / 100	625 ms	133560 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() + 2, 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;
    }

    struct cmp1{
        bool operator () (const Circle &a, const Circle &b) const{
            if (a.x == b.x) {
                if (a.y == b.y) {
                    if (a.r == b.r) return a.id < b.id;
                    return a.r < b.r;
                }
                return a.y < b.y;
            }
            return a.x < b.x;
        }
    };

    struct cmp2{
        bool operator () (const Circle &a, const Circle &b) const{
            if (a.y == b.y) {
                if (a.x == b.x) {
                    if (a.r == b.r) return a.id < b.id;
                    return a.r < b.r;
                }
                return a.x < b.x;
            }
            return a.y < b.y;
        }
    };

    struct cmp3{
        bool operator () (const Circle &a, const Circle &b) const{
            if (a.r == b.r) {
                if (a.id == b.id) {
                    if (a.y == b.y) return a.x < b.x;
                    return a.y < b.y;
                }
                return a.id > b.id;
            }
            return a.r < b.r;
        }
    };

    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));
//            cout << cur << ' ' << delId << endl;

            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;
//                cout << "X: " << id1 << ' ' << idC << ' ' << endl;
                eraseList.pb(idC);
                sortX.toDelete(id1);

                int delId = sortY.lb(ii(circle[idC].y, circle[idC].id));
                sortY.toDelete(delId);
            }
//            cout << endl;

            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;
//                cout << "Y: " << id1 << ' ' << idC << ' ' << endl;

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

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

            for(auto p: eraseList){
                answer[p] = delId;
//                cout << p << ' ';
                int id = sortR.rb(ii(circle[p].r, circle[p].id));
//                cout << id << endl;
                sortR.toDelete(id + 1, -1);
            }
//            cout << endl;
            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)
    **/
    void solve(){

    }
}


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 (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:242: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]
  242 |             for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:244: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]
  244 |                 if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:257: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]
  257 |             for(;id1 < sortY.grid.size() and sortY.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:259: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]
  259 |                 if (id1 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:466: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]
  466 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:472: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]
  472 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:474: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]
  474 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:469:25: warning: unused variable 'cnt' [-Wunused-variable]
  469 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: At global scope:
circle_selection.cpp:535:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  535 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:539:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  539 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:540:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  540 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	63312 KB	Output is correct
2	Correct	35 ms	63568 KB	Output is correct
3	Correct	37 ms	63428 KB	Output is correct
4	Correct	34 ms	63432 KB	Output is correct
5	Correct	41 ms	63576 KB	Output is correct
6	Correct	40 ms	63572 KB	Output is correct
7	Correct	36 ms	63572 KB	Output is correct
8	Correct	44 ms	63568 KB	Output is correct
9	Correct	40 ms	63572 KB	Output is correct
10	Correct	40 ms	63580 KB	Output is correct
11	Correct	42 ms	63572 KB	Output is correct
12	Correct	42 ms	63572 KB	Output is correct
13	Correct	42 ms	63576 KB	Output is correct
14	Correct	38 ms	63572 KB	Output is correct
15	Correct	41 ms	63428 KB	Output is correct
16	Correct	45 ms	63580 KB	Output is correct
17	Correct	44 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	75 ms	63648 KB	Output is correct
20	Correct	74 ms	63612 KB	Output is correct
21	Correct	75 ms	63568 KB	Output is correct
22	Correct	101 ms	63744 KB	Output is correct
23	Correct	105 ms	63764 KB	Output is correct
24	Correct	98 ms	63568 KB	Output is correct
25	Correct	97 ms	63744 KB	Output is correct
26	Correct	97 ms	63656 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	362 ms	106476 KB	Output is correct
2	Correct	363 ms	100896 KB	Output is correct
3	Correct	357 ms	101352 KB	Output is correct
4	Correct	344 ms	104432 KB	Output is correct
5	Correct	313 ms	92904 KB	Output is correct
6	Correct	354 ms	93420 KB	Output is correct
7	Correct	318 ms	93160 KB	Output is correct
8	Correct	325 ms	93160 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	63356 KB	Output is correct
2	Correct	153 ms	85976 KB	Output is correct
3	Correct	485 ms	133560 KB	Output is correct
4	Correct	491 ms	133248 KB	Output is correct
5	Correct	547 ms	133308 KB	Output is correct
6	Correct	299 ms	98788 KB	Output is correct
7	Correct	146 ms	81888 KB	Output is correct
8	Correct	57 ms	67320 KB	Output is correct
9	Correct	519 ms	133320 KB	Output is correct
10	Correct	625 ms	133560 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	592 ms	106164 KB	Output is correct
2	Correct	594 ms	109756 KB	Output is correct
3	Correct	430 ms	104888 KB	Output is correct
4	Correct	563 ms	109240 KB	Output is correct
5	Correct	543 ms	110008 KB	Output is correct
6	Correct	412 ms	103784 KB	Output is correct

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	63312 KB	Output is correct
2	Correct	35 ms	63568 KB	Output is correct
3	Correct	37 ms	63428 KB	Output is correct
4	Correct	34 ms	63432 KB	Output is correct
5	Correct	41 ms	63576 KB	Output is correct
6	Correct	40 ms	63572 KB	Output is correct
7	Correct	36 ms	63572 KB	Output is correct
8	Correct	44 ms	63568 KB	Output is correct
9	Correct	40 ms	63572 KB	Output is correct
10	Correct	40 ms	63580 KB	Output is correct
11	Correct	42 ms	63572 KB	Output is correct
12	Correct	42 ms	63572 KB	Output is correct
13	Correct	42 ms	63576 KB	Output is correct
14	Correct	38 ms	63572 KB	Output is correct
15	Correct	41 ms	63428 KB	Output is correct
16	Correct	45 ms	63580 KB	Output is correct
17	Correct	44 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	75 ms	63648 KB	Output is correct
20	Correct	74 ms	63612 KB	Output is correct
21	Correct	75 ms	63568 KB	Output is correct
22	Correct	101 ms	63744 KB	Output is correct
23	Correct	105 ms	63764 KB	Output is correct
24	Correct	98 ms	63568 KB	Output is correct
25	Correct	97 ms	63744 KB	Output is correct
26	Correct	97 ms	63656 KB	Output is correct
27	Incorrect	52 ms	65796 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	63312 KB	Output is correct
2	Correct	35 ms	63568 KB	Output is correct
3	Correct	37 ms	63428 KB	Output is correct
4	Correct	34 ms	63432 KB	Output is correct
5	Correct	41 ms	63576 KB	Output is correct
6	Correct	40 ms	63572 KB	Output is correct
7	Correct	36 ms	63572 KB	Output is correct
8	Correct	44 ms	63568 KB	Output is correct
9	Correct	40 ms	63572 KB	Output is correct
10	Correct	40 ms	63580 KB	Output is correct
11	Correct	42 ms	63572 KB	Output is correct
12	Correct	42 ms	63572 KB	Output is correct
13	Correct	42 ms	63576 KB	Output is correct
14	Correct	38 ms	63572 KB	Output is correct
15	Correct	41 ms	63428 KB	Output is correct
16	Correct	45 ms	63580 KB	Output is correct
17	Correct	44 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	75 ms	63648 KB	Output is correct
20	Correct	74 ms	63612 KB	Output is correct
21	Correct	75 ms	63568 KB	Output is correct
22	Correct	101 ms	63744 KB	Output is correct
23	Correct	105 ms	63764 KB	Output is correct
24	Correct	98 ms	63568 KB	Output is correct
25	Correct	97 ms	63744 KB	Output is correct
26	Correct	97 ms	63656 KB	Output is correct
27	Correct	362 ms	106476 KB	Output is correct
28	Correct	363 ms	100896 KB	Output is correct
29	Correct	357 ms	101352 KB	Output is correct
30	Correct	344 ms	104432 KB	Output is correct
31	Correct	313 ms	92904 KB	Output is correct
32	Correct	354 ms	93420 KB	Output is correct
33	Correct	318 ms	93160 KB	Output is correct
34	Correct	325 ms	93160 KB	Output is correct
35	Correct	35 ms	63356 KB	Output is correct
36	Correct	153 ms	85976 KB	Output is correct
37	Correct	485 ms	133560 KB	Output is correct
38	Correct	491 ms	133248 KB	Output is correct
39	Correct	547 ms	133308 KB	Output is correct
40	Correct	299 ms	98788 KB	Output is correct
41	Correct	146 ms	81888 KB	Output is correct
42	Correct	57 ms	67320 KB	Output is correct
43	Correct	519 ms	133320 KB	Output is correct
44	Correct	625 ms	133560 KB	Output is correct
45	Correct	592 ms	106164 KB	Output is correct
46	Correct	594 ms	109756 KB	Output is correct
47	Correct	430 ms	104888 KB	Output is correct
48	Correct	563 ms	109240 KB	Output is correct
49	Correct	543 ms	110008 KB	Output is correct
50	Correct	412 ms	103784 KB	Output is correct
51	Incorrect	52 ms	65796 KB	Output isn't correct
52	Halted	0 ms	0 KB	-