oj.uz

Submission #1097913

# Submission time Handle Problem Language Result Execution time Memory
1097913 2024-10-08T15:35:08 Z Requiem Circle selection (APIO18_circle_selection) C++17
45 / 100
 3000 ms 133820 KB 
#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() ;
    }

    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.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 = 0;
        while(cur < n){
            cur = sortR.remaining.root(cur);
            if (cur == n) 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 << ' ' << circle[delId].x << ' ' << circle[delId].r << 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 << ' ';
                sortR.toDelete(p - 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:227: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]
  227 |             for(;id1 < sortX.grid.size() and sortX.grid[id1].fi <= R;){
      |                  ~~~~^~~~~~~~~~~~~~~~~~~
circle_selection.cpp:229: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]
  229 |                 if (id1 >= sortX.grid.size() or sortX.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
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 < sortY.grid.size() and sortY.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 >= sortY.grid.size() or sortY.grid[id1].fi > R) continue;
      |                     ~~~~^~~~~~~~~~~~~~~~~~~~
circle_selection.cpp: In function 'void subtask4::solve()':
circle_selection.cpp:449: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]
  449 |                 if (valX != listX.size() and listX[valX] == nx){
      |                     ~~~~~^~~~~~~~~~~~~~~
circle_selection.cpp:455: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]
  455 |                     for(;id1 < grid[valX].grid.size() and grid[valX].grid[id1].fi <= discreteY + 2;){
      |                          ~~~~^~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:457: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]
  457 |                         if (id1 >= grid[valX].grid.size()) continue;
      |                             ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:452:25: warning: unused variable 'cnt' [-Wunused-variable]
  452 |                     int cnt = 0;
      |                         ^~~
circle_selection.cpp: At global scope:
circle_selection.cpp:518:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  518 | main()
      | ^~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:522:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  522 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:523:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  523 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63572 KB Output is correct
2 Correct 41 ms 63412 KB Output is correct
3 Correct 39 ms 63568 KB Output is correct
4 Correct 41 ms 63320 KB Output is correct
5 Correct 40 ms 63568 KB Output is correct
6 Correct 42 ms 63572 KB Output is correct
7 Correct 39 ms 63572 KB Output is correct
8 Correct 38 ms 63528 KB Output is correct
9 Correct 42 ms 63568 KB Output is correct
10 Correct 41 ms 63576 KB Output is correct
11 Correct 43 ms 63572 KB Output is correct
12 Correct 47 ms 63572 KB Output is correct
13 Correct 40 ms 63568 KB Output is correct
14 Correct 41 ms 63572 KB Output is correct
15 Correct 40 ms 63572 KB Output is correct
16 Correct 42 ms 63572 KB Output is correct
17 Correct 42 ms 63568 KB Output is correct
18 Correct 43 ms 63572 KB Output is correct
19 Correct 81 ms 63544 KB Output is correct
20 Correct 74 ms 63572 KB Output is correct
21 Correct 73 ms 63576 KB Output is correct
22 Correct 98 ms 63660 KB Output is correct
23 Correct 99 ms 63572 KB Output is correct
24 Correct 102 ms 63720 KB Output is correct
25 Correct 100 ms 63744 KB Output is correct
26 Correct 98 ms 63716 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 90876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 63572 KB Output is correct
2 Correct 167 ms 85928 KB Output is correct
3 Correct 492 ms 133564 KB Output is correct
4 Correct 486 ms 133564 KB Output is correct
5 Correct 578 ms 133308 KB Output is correct
6 Correct 295 ms 99000 KB Output is correct
7 Correct 148 ms 81876 KB Output is correct
8 Correct 60 ms 67324 KB Output is correct
9 Correct 507 ms 133560 KB Output is correct
10 Correct 603 ms 133820 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 106372 KB Output is correct
2 Correct 561 ms 109752 KB Output is correct
3 Correct 443 ms 105144 KB Output is correct
4 Correct 616 ms 109244 KB Output is correct
5 Correct 579 ms 110004 KB Output is correct
6 Correct 389 ms 103860 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63572 KB Output is correct
2 Correct 41 ms 63412 KB Output is correct
3 Correct 39 ms 63568 KB Output is correct
4 Correct 41 ms 63320 KB Output is correct
5 Correct 40 ms 63568 KB Output is correct
6 Correct 42 ms 63572 KB Output is correct
7 Correct 39 ms 63572 KB Output is correct
8 Correct 38 ms 63528 KB Output is correct
9 Correct 42 ms 63568 KB Output is correct
10 Correct 41 ms 63576 KB Output is correct
11 Correct 43 ms 63572 KB Output is correct
12 Correct 47 ms 63572 KB Output is correct
13 Correct 40 ms 63568 KB Output is correct
14 Correct 41 ms 63572 KB Output is correct
15 Correct 40 ms 63572 KB Output is correct
16 Correct 42 ms 63572 KB Output is correct
17 Correct 42 ms 63568 KB Output is correct
18 Correct 43 ms 63572 KB Output is correct
19 Correct 81 ms 63544 KB Output is correct
20 Correct 74 ms 63572 KB Output is correct
21 Correct 73 ms 63576 KB Output is correct
22 Correct 98 ms 63660 KB Output is correct
23 Correct 99 ms 63572 KB Output is correct
24 Correct 102 ms 63720 KB Output is correct
25 Correct 100 ms 63744 KB Output is correct
26 Correct 98 ms 63716 KB Output is correct
27 Incorrect 51 ms 65932 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63572 KB Output is correct
2 Correct 41 ms 63412 KB Output is correct
3 Correct 39 ms 63568 KB Output is correct
4 Correct 41 ms 63320 KB Output is correct
5 Correct 40 ms 63568 KB Output is correct
6 Correct 42 ms 63572 KB Output is correct
7 Correct 39 ms 63572 KB Output is correct
8 Correct 38 ms 63528 KB Output is correct
9 Correct 42 ms 63568 KB Output is correct
10 Correct 41 ms 63576 KB Output is correct
11 Correct 43 ms 63572 KB Output is correct
12 Correct 47 ms 63572 KB Output is correct
13 Correct 40 ms 63568 KB Output is correct
14 Correct 41 ms 63572 KB Output is correct
15 Correct 40 ms 63572 KB Output is correct
16 Correct 42 ms 63572 KB Output is correct
17 Correct 42 ms 63568 KB Output is correct
18 Correct 43 ms 63572 KB Output is correct
19 Correct 81 ms 63544 KB Output is correct
20 Correct 74 ms 63572 KB Output is correct
21 Correct 73 ms 63576 KB Output is correct
22 Correct 98 ms 63660 KB Output is correct
23 Correct 99 ms 63572 KB Output is correct
24 Correct 102 ms 63720 KB Output is correct
25 Correct 100 ms 63744 KB Output is correct
26 Correct 98 ms 63716 KB Output is correct
27 Execution timed out 3053 ms 90876 KB Time limit exceeded
28 Halted 0 ms 0 KB -