답안 #1097883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097883	2024-10-08T14:04:03 Z	Requiem	원 고르기 (APIO18_circle_selection)	C++17	57 / 100	1155 ms	159384 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 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){
            if (lab[u] > lab[v] and small_to_large) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
        }
    }
};
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;
        }
    };

    set<Circle, cmp1> sortX;
    set<Circle, cmp2> sortY;
    set<Circle, cmp3> 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;
//            cout << circle[i].x << ' ' << circle[i].y << ' ' << circle[i].r << endl;
            sortX.insert(circle[i]);
            sortY.insert(circle[i]);
            sortR.insert(circle[i]);
        }
        vector<Circle> eraseList;

        while (sortR.size() > 0){
            eraseList.clear();
            Circle ToErase = *sortR.rbegin();
            int L = ToErase.x;
            int R = ToErase.y;
//            cerr << ToErase.id << ' ' << endl;

            auto s1 = sortX.lower_bound(Circle(L, -inf, -inf, -inf));
            while(s1 != sortX.end() and (*s1).x <= R){
                eraseList.pb(*s1);
//                cerr << "X: " << (*s1).x << ' ' << (*s1).id << endl;
                s1++;
            }

            auto s2 = sortY.lower_bound(Circle(-inf, L, -inf, -inf));
            while(s2 != sortY.end() and (*s2).y <= R){
//                cerr << "Y: " << (*s2).y << ' ' << (*s2).id << endl;

                eraseList.pb(*s2);
                s2++;
            }
            for(auto p: eraseList){
                answer[p.id] = ToErase.id;
                auto it1 = sortX.find(p);
                auto it2 = sortY.find(p);
                auto it3 = sortR.find(p);
//                cout << p.id << ' ';
                if (it1 != sortX.end()) sortX.erase(it1);
                if (it2 != sortY.end()) sortY.erase(it2);
                if (it3 != sortR.end()) sortR.erase(it3);
            }
//            cout << endl;
        }

        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)

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

        void toDelete(int l){  //xoa 1 doan [l, r]
            remaining.unite(l + 1, l);
        }
    };

    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 subtask4::solve()':
circle_selection.cpp:425: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]
  425 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:431: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]
  431 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:433: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]
  433 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:428:25: warning: unused variable 'cnt' [-Wunused-variable]
  428 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: At global scope:
circle_selection.cpp:494:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  494 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:498:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  498 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:499:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  499 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	63480 KB	Output is correct
2	Correct	39 ms	63580 KB	Output is correct
3	Correct	39 ms	63372 KB	Output is correct
4	Correct	40 ms	63316 KB	Output is correct
5	Correct	38 ms	63416 KB	Output is correct
6	Correct	39 ms	63448 KB	Output is correct
7	Correct	39 ms	63332 KB	Output is correct
8	Correct	38 ms	63572 KB	Output is correct
9	Correct	39 ms	63568 KB	Output is correct
10	Correct	42 ms	63568 KB	Output is correct
11	Correct	37 ms	63564 KB	Output is correct
12	Correct	35 ms	63524 KB	Output is correct
13	Correct	40 ms	63572 KB	Output is correct
14	Correct	38 ms	63568 KB	Output is correct
15	Correct	41 ms	63576 KB	Output is correct
16	Correct	41 ms	63568 KB	Output is correct
17	Correct	46 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	70 ms	63568 KB	Output is correct
20	Correct	72 ms	63568 KB	Output is correct
21	Correct	75 ms	63732 KB	Output is correct
22	Correct	92 ms	63568 KB	Output is correct
23	Correct	95 ms	63744 KB	Output is correct
24	Correct	92 ms	63568 KB	Output is correct
25	Correct	92 ms	63580 KB	Output is correct
26	Correct	92 ms	63580 KB	Output is correct

Subtask #2

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	994 ms	158852 KB	Output is correct
2	Correct	1093 ms	152744 KB	Output is correct
3	Correct	1155 ms	157096 KB	Output is correct
4	Correct	1128 ms	159384 KB	Output is correct
5	Correct	1016 ms	142908 KB	Output is correct
6	Correct	944 ms	142904 KB	Output is correct
7	Correct	987 ms	142932 KB	Output is correct
8	Correct	972 ms	142884 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	43 ms	63568 KB	Output is correct
2	Correct	164 ms	86488 KB	Output is correct
3	Correct	493 ms	133992 KB	Output is correct
4	Correct	502 ms	133920 KB	Output is correct
5	Correct	555 ms	133920 KB	Output is correct
6	Correct	302 ms	99372 KB	Output is correct
7	Correct	150 ms	82392 KB	Output is correct
8	Correct	60 ms	67832 KB	Output is correct
9	Correct	491 ms	133928 KB	Output is correct
10	Correct	589 ms	134332 KB	Output is correct

Subtask #4

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	599 ms	106912 KB	Output is correct
2	Correct	579 ms	110268 KB	Output is correct
3	Correct	454 ms	105660 KB	Output is correct
4	Correct	609 ms	109908 KB	Output is correct
5	Correct	595 ms	110516 KB	Output is correct
6	Correct	456 ms	104372 KB	Output is correct

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	63480 KB	Output is correct
2	Correct	39 ms	63580 KB	Output is correct
3	Correct	39 ms	63372 KB	Output is correct
4	Correct	40 ms	63316 KB	Output is correct
5	Correct	38 ms	63416 KB	Output is correct
6	Correct	39 ms	63448 KB	Output is correct
7	Correct	39 ms	63332 KB	Output is correct
8	Correct	38 ms	63572 KB	Output is correct
9	Correct	39 ms	63568 KB	Output is correct
10	Correct	42 ms	63568 KB	Output is correct
11	Correct	37 ms	63564 KB	Output is correct
12	Correct	35 ms	63524 KB	Output is correct
13	Correct	40 ms	63572 KB	Output is correct
14	Correct	38 ms	63568 KB	Output is correct
15	Correct	41 ms	63576 KB	Output is correct
16	Correct	41 ms	63568 KB	Output is correct
17	Correct	46 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	70 ms	63568 KB	Output is correct
20	Correct	72 ms	63568 KB	Output is correct
21	Correct	75 ms	63732 KB	Output is correct
22	Correct	92 ms	63568 KB	Output is correct
23	Correct	95 ms	63744 KB	Output is correct
24	Correct	92 ms	63568 KB	Output is correct
25	Correct	92 ms	63580 KB	Output is correct
26	Correct	92 ms	63580 KB	Output is correct
27	Incorrect	56 ms	66296 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Subtask #6

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	63480 KB	Output is correct
2	Correct	39 ms	63580 KB	Output is correct
3	Correct	39 ms	63372 KB	Output is correct
4	Correct	40 ms	63316 KB	Output is correct
5	Correct	38 ms	63416 KB	Output is correct
6	Correct	39 ms	63448 KB	Output is correct
7	Correct	39 ms	63332 KB	Output is correct
8	Correct	38 ms	63572 KB	Output is correct
9	Correct	39 ms	63568 KB	Output is correct
10	Correct	42 ms	63568 KB	Output is correct
11	Correct	37 ms	63564 KB	Output is correct
12	Correct	35 ms	63524 KB	Output is correct
13	Correct	40 ms	63572 KB	Output is correct
14	Correct	38 ms	63568 KB	Output is correct
15	Correct	41 ms	63576 KB	Output is correct
16	Correct	41 ms	63568 KB	Output is correct
17	Correct	46 ms	63572 KB	Output is correct
18	Correct	46 ms	63572 KB	Output is correct
19	Correct	70 ms	63568 KB	Output is correct
20	Correct	72 ms	63568 KB	Output is correct
21	Correct	75 ms	63732 KB	Output is correct
22	Correct	92 ms	63568 KB	Output is correct
23	Correct	95 ms	63744 KB	Output is correct
24	Correct	92 ms	63568 KB	Output is correct
25	Correct	92 ms	63580 KB	Output is correct
26	Correct	92 ms	63580 KB	Output is correct
27	Correct	994 ms	158852 KB	Output is correct
28	Correct	1093 ms	152744 KB	Output is correct
29	Correct	1155 ms	157096 KB	Output is correct
30	Correct	1128 ms	159384 KB	Output is correct
31	Correct	1016 ms	142908 KB	Output is correct
32	Correct	944 ms	142904 KB	Output is correct
33	Correct	987 ms	142932 KB	Output is correct
34	Correct	972 ms	142884 KB	Output is correct
35	Correct	43 ms	63568 KB	Output is correct
36	Correct	164 ms	86488 KB	Output is correct
37	Correct	493 ms	133992 KB	Output is correct
38	Correct	502 ms	133920 KB	Output is correct
39	Correct	555 ms	133920 KB	Output is correct
40	Correct	302 ms	99372 KB	Output is correct
41	Correct	150 ms	82392 KB	Output is correct
42	Correct	60 ms	67832 KB	Output is correct
43	Correct	491 ms	133928 KB	Output is correct
44	Correct	589 ms	134332 KB	Output is correct
45	Correct	599 ms	106912 KB	Output is correct
46	Correct	579 ms	110268 KB	Output is correct
47	Correct	454 ms	105660 KB	Output is correct
48	Correct	609 ms	109908 KB	Output is correct
49	Correct	595 ms	110516 KB	Output is correct
50	Correct	456 ms	104372 KB	Output is correct
51	Incorrect	56 ms	66296 KB	Output isn't correct
52	Halted	0 ms	0 KB	-