oj.uz

Submission #1098055

# Submission time Handle Problem Language Result Execution time Memory
1098055 2024-10-09T01:48:30 Z Requiem Circle selection (APIO18_circle_selection) C++17
100 / 100
 922 ms 150172 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() + 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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