oj.uz

Submission #824914

# Submission time Handle Problem Language Result Execution time Memory
824914 2023-08-14T11:51:33 Z andrei_boaca Fountain Parks (IOI21_parks) C++17
70 / 100
 3500 ms 137500 KB 
#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;

typedef pair<int,int> pii;
map<pii,int> ind;
map<pii,int> ocup;
map<pii,int> match;
struct point
{
    int x,y;
} v[200005];
int k;
vector<int> myy[200005];
vector<int> muchii[200005];
vector<pii> edges;
bool have[11][200005];
bool use[200005];
void dfs(int nod)
{
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
            dfs(i);
}
int c[11][200005];
vector<int> U,V,A,B;
void addedge(int xa,int ya,int xb,int yb,int xc,int yc)
{
    int a=ind[{xa,ya}];
    int b=ind[{xb,yb}];
    U.push_back(a);
    V.push_back(b);
    muchii[a].push_back(b);
    muchii[b].push_back(a);
    A.push_back(xc);
    B.push_back(yc);
}
int diri[5]={-2,2,0,0};
int dirj[5]={0,0,-2,2};
int nr;
vector<int> cedge[800005];
int l[800005],r[800005];
vector<pii> who;
bool pairup(int nod)
{
    if(use[nod])
        return 0;
    use[nod]=1;
    for(int i:cedge[nod])
        if(r[i]==0)
        {
            l[nod]=i;
            r[i]=nod;
            return 1;
        }
    for(int i:cedge[nod])
        if(pairup(r[i]))
        {
            l[nod]=i;
            r[i]=nod;
            return 1;
        }
    return 0;
}
int comp[700005];
vector<int> dsu[700005];
void dsu_merge(int c1,int c2)
{
    if(dsu[c1].size()<dsu[c2].size())
        swap(c1,c2);
    for(int i:dsu[c2])
    {
        comp[i]=c1;
        dsu[c1].push_back(i);
    }
    dsu[c2].clear();
}
int construct_roads(std::vector<int> X, std::vector<int> Y)
{
    k=X.size();
    int xmax=0;
    for(int i=0;i<k;i++)
    {
        v[i]={X[i],Y[i]};
        ind[{X[i],Y[i]}]=i;
        xmax=max(xmax,X[i]);
        if(X[i]<=6)
        {
            myy[X[i]].push_back(Y[i]);
            have[X[i]][Y[i]]=1;
        }
    }
    if(xmax<=2)
    {
        sort(myy[2].begin(),myy[2].end());
        vector<int> U,V,a,b;
        for(int i=1;i<myy[2].size();i++)
        {
            if(myy[2][i]-myy[2][i-1]!=2)
                return 0;
            int x=2;
            int yu=myy[2][i-1];
            int yv=myy[2][i];
            U.push_back(ind[{x,yu}]);
            V.push_back(ind[{x,yv}]);
            a.push_back(x-1);
            b.push_back(yv-1);
        }
        build(U,V,a,b);
        return 1;
    }
    if(xmax<=4)
    {
        sort(myy[2].begin(),myy[2].end());
        sort(myy[4].begin(),myy[4].end());
        vector<int> U,V,A,B;
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[2][i-2])
            {
                int a=ind[{2,i}];
                int b=ind[{2,i-2}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(1);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[4][i]&&have[4][i-2])
            {
                int a=ind[{4,i}];
                int b=ind[{4,i-2}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(5);
                B.push_back(i-1);
            }
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[4][i])
            {
                int a=ind[{2,i}];
                int b=ind[{4,i}];
                U.push_back(a);
                V.push_back(b);
                muchii[a].push_back(b);
                muchii[b].push_back(a);
                A.push_back(3);
                B.push_back(i+1);
            }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                return 0;
        build(U,V,A,B);
        return 1;
    }
    if(xmax<=6)
    {
        sort(myy[2].begin(),myy[2].end());
        sort(myy[4].begin(),myy[4].end());
        sort(myy[6].begin(),myy[6].end());
        int nr=0;
        for(int i=2;i<=200000;i+=2)
            if(have[2][i])
            {
                if(have[2][i-2])
                {
                    addedge(2,i,2,i-2,1,i-1);
                    c[2][i]=c[2][i-2];
                }
                else
                {
                    nr++;
                    c[2][i]=nr;
                }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[6][i])
            {
                if(have[6][i-2])
                {
                    addedge(6,i,6,i-2,7,i-1);
                    c[6][i]=c[6][i-2];
                }
                else
                {
                    nr++;
                    c[6][i]=nr;
                }
            }
        int lft=1;
        for(int i=2;i<=200000;i+=2)
            if(have[4][i])
            {
                if(have[4][i-2])
                {
                    if(lft==1)
                    {
                        addedge(4,i,4,i-2,3,i-1);
                        ocup[{3,i-1}]=1;
                    }
                    else
                    {
                        addedge(4,i,4,i-2,5,i-1);
                        ocup[{5,i-1}]=1;
                    }
                    lft^=1;
                    c[4][i]=c[4][i-2];
                }
                else
                {
                    lft=1;
                    nr++;
                    c[4][i]=nr;
                }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[2][i]&&have[4][i])
            {
                int a=c[2][i];
                int b=c[4][i];
                if(match[{a,b}]==0)
                    {
                        match[{a,b}]=1;
                        if(!ocup[{3,i-1}])
                            {
                                addedge(2,i,4,i,3,i-1);
                                ocup[{3,i-1}]=1;
                            }
                        else
                        {
                            addedge(2,i,4,i,3,i+1);
                            ocup[{3,i+1}]=1;
                        }
                    }
            }
        for(int i=2;i<=200000;i+=2)
            if(have[4][i]&&have[6][i])
            {
                int a=c[4][i];
                int b=c[6][i];
                if(match[{a,b}]==0)
                    {
                        match[{a,b}]=1;
                        if(!ocup[{5,i-1}])
                            {
                                addedge(4,i,6,i,5,i-1);
                                ocup[{5,i-1}]=1;
                            }
                        else
                        {
                            addedge(4,i,6,i,5,i+1);
                            ocup[{5,i+1}]=1;
                        }
                    }
            }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                return 0;
        build(U,V,A,B);
        return 1;
    }
    vector<int> nodes;
    for(int i=0;i<k;i++)
        nodes.push_back(i);
    int bulan=0;
    nr=0;
    while(bulan<=4)
    {
        random_shuffle(nodes.begin(),nodes.end());
        bulan++;
        bool good=1;
        for(int i=0;i<k;i++)
        {
            comp[i]=i;
            dsu[i].clear();
            dsu[i].push_back(i);
            muchii[i].clear();
            use[i]=0;
        }
        edges.clear();
        for(auto p:nodes)
        {
            int nod=p;
            int x=X[nod];
            int y=Y[nod];
            for(int z=0;z<4;z++)
            {
                int lin=x+diri[z];
                int col=y+dirj[z];
                if(ind.count({lin,col})!=0)
                    {
                        int w=ind[{lin,col}];
                        if(comp[nod]!=comp[w])
                        {
                            dsu_merge(comp[nod],comp[w]);
                            muchii[nod].push_back(w);
                            muchii[w].push_back(nod);
                            edges.push_back({nod,w});
                        }
                    }
            }
        }
        dfs(0);
        for(int i=0;i<k;i++)
            if(!use[i])
                good=0;
        if(good==0)
            continue;
        who.clear();
        who.push_back({0,0});
        for(int i=0;i<edges.size();i++)
        {
            cedge[i+1].clear();
            int a=edges[i].first;
            int b=edges[i].second;
            int xa=X[a],ya=Y[a],xb=X[b],yb=Y[b];
            if(xa==xb)
            {
                int x=xa+1;
                int y=(ya+yb)/2;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                int nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);

                x=xa-1;
                y=(ya+yb)/2;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);
            }
            else
            {
                int x=(xa+xb)/2;
                int y=ya-1;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                int nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);

                x=(xa+xb)/2;
                y=ya+1;
                if(ind[{x,y}]==0)
                    {
                        nr++;
                        ind[{x,y}]=nr;
                        who.push_back({x,y});
                    }
                nrm=ind[{x,y}];
                cedge[i+1].push_back(nrm);
            }
        }
        for(int i=1;i<=edges.size();i++)
            l[i]=0;
        for(int i=1;i<=nr;i++)
            r[i]=0;
        bool ok=0;
        do
        {
            ok=0;
            for(int i=1;i<=edges.size();i++)
                use[i]=0;
            for(int i=1;i<=edges.size();i++)
                if(l[i]==0)
                    ok|=pairup(i);
        }while(ok);
        for(int i=1;i<=edges.size();i++)
            if(l[i]==0)
                good=0;
        if(good==0)
            continue;
        for(int i=1;i<=edges.size();i++)
        {
            U.push_back(edges[i-1].first);
            V.push_back(edges[i-1].second);
            A.push_back(who[l[i]].first);
            B.push_back(who[l[i]].second);
        }
        build(U,V,A,B);
        return 1;
    }
    return 0;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i=1;i<myy[2].size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:318:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  318 |         for(int i=0;i<edges.size();i++)
      |                     ~^~~~~~~~~~~~~
parks.cpp:373:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  373 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:381:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  381 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:383:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  383 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:387:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  387 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:392:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  392 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct
17 Correct 23 ms 44884 KB Output is correct
18 Correct 27 ms 44884 KB Output is correct
19 Correct 25 ms 44960 KB Output is correct
20 Correct 22 ms 44884 KB Output is correct
21 Correct 21 ms 44900 KB Output is correct
22 Correct 21 ms 44884 KB Output is correct
23 Correct 320 ms 87320 KB Output is correct
24 Correct 24 ms 44904 KB Output is correct
25 Correct 25 ms 45196 KB Output is correct
26 Correct 26 ms 45396 KB Output is correct
27 Correct 29 ms 45644 KB Output is correct
28 Correct 148 ms 61940 KB Output is correct
29 Correct 192 ms 70440 KB Output is correct
30 Correct 238 ms 78820 KB Output is correct
31 Correct 373 ms 87432 KB Output is correct
32 Correct 21 ms 44856 KB Output is correct
33 Correct 19 ms 44852 KB Output is correct
34 Correct 19 ms 44920 KB Output is correct
35 Correct 30 ms 44844 KB Output is correct
36 Correct 23 ms 44880 KB Output is correct
37 Correct 23 ms 44856 KB Output is correct
38 Correct 21 ms 44856 KB Output is correct
39 Correct 24 ms 44896 KB Output is correct
40 Correct 21 ms 44864 KB Output is correct
41 Correct 20 ms 44884 KB Output is correct
42 Correct 24 ms 44876 KB Output is correct
43 Correct 21 ms 45268 KB Output is correct
44 Correct 25 ms 45408 KB Output is correct
45 Correct 185 ms 63160 KB Output is correct
46 Correct 244 ms 71712 KB Output is correct
47 Correct 184 ms 71640 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct
17 Correct 23 ms 44884 KB Output is correct
18 Correct 27 ms 44884 KB Output is correct
19 Correct 25 ms 44960 KB Output is correct
20 Correct 22 ms 44884 KB Output is correct
21 Correct 21 ms 44900 KB Output is correct
22 Correct 21 ms 44884 KB Output is correct
23 Correct 320 ms 87320 KB Output is correct
24 Correct 24 ms 44904 KB Output is correct
25 Correct 25 ms 45196 KB Output is correct
26 Correct 26 ms 45396 KB Output is correct
27 Correct 29 ms 45644 KB Output is correct
28 Correct 148 ms 61940 KB Output is correct
29 Correct 192 ms 70440 KB Output is correct
30 Correct 238 ms 78820 KB Output is correct
31 Correct 373 ms 87432 KB Output is correct
32 Correct 21 ms 44856 KB Output is correct
33 Correct 19 ms 44852 KB Output is correct
34 Correct 19 ms 44920 KB Output is correct
35 Correct 30 ms 44844 KB Output is correct
36 Correct 23 ms 44880 KB Output is correct
37 Correct 23 ms 44856 KB Output is correct
38 Correct 21 ms 44856 KB Output is correct
39 Correct 24 ms 44896 KB Output is correct
40 Correct 21 ms 44864 KB Output is correct
41 Correct 20 ms 44884 KB Output is correct
42 Correct 24 ms 44876 KB Output is correct
43 Correct 21 ms 45268 KB Output is correct
44 Correct 25 ms 45408 KB Output is correct
45 Correct 185 ms 63160 KB Output is correct
46 Correct 244 ms 71712 KB Output is correct
47 Correct 184 ms 71640 KB Output is correct
48 Correct 25 ms 44884 KB Output is correct
49 Correct 23 ms 44892 KB Output is correct
50 Correct 24 ms 44956 KB Output is correct
51 Correct 24 ms 44884 KB Output is correct
52 Correct 30 ms 44880 KB Output is correct
53 Correct 31 ms 44884 KB Output is correct
54 Correct 29 ms 44880 KB Output is correct
55 Correct 368 ms 86928 KB Output is correct
56 Correct 25 ms 44876 KB Output is correct
57 Correct 26 ms 45324 KB Output is correct
58 Correct 36 ms 46332 KB Output is correct
59 Correct 31 ms 46784 KB Output is correct
60 Correct 157 ms 65608 KB Output is correct
61 Correct 215 ms 74236 KB Output is correct
62 Correct 252 ms 79580 KB Output is correct
63 Correct 311 ms 86512 KB Output is correct
64 Correct 28 ms 44856 KB Output is correct
65 Correct 28 ms 44952 KB Output is correct
66 Correct 21 ms 44936 KB Output is correct
67 Correct 299 ms 83220 KB Output is correct
68 Correct 305 ms 83344 KB Output is correct
69 Correct 286 ms 83492 KB Output is correct
70 Correct 33 ms 45788 KB Output is correct
71 Correct 34 ms 46696 KB Output is correct
72 Correct 158 ms 69288 KB Output is correct
73 Correct 294 ms 82056 KB Output is correct
74 Correct 385 ms 93776 KB Output is correct
75 Correct 415 ms 95908 KB Output is correct
76 Correct 308 ms 84220 KB Output is correct
77 Correct 29 ms 46036 KB Output is correct
78 Correct 36 ms 46976 KB Output is correct
79 Correct 159 ms 70296 KB Output is correct
80 Correct 313 ms 82996 KB Output is correct
81 Correct 415 ms 95592 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct
17 Correct 31 ms 44896 KB Output is correct
18 Correct 23 ms 44884 KB Output is correct
19 Correct 23 ms 44896 KB Output is correct
20 Correct 1055 ms 122084 KB Output is correct
21 Correct 1045 ms 121644 KB Output is correct
22 Correct 1127 ms 120692 KB Output is correct
23 Correct 870 ms 122556 KB Output is correct
24 Correct 1450 ms 70716 KB Output is correct
25 Correct 3406 ms 94056 KB Output is correct
26 Correct 2764 ms 93824 KB Output is correct
27 Correct 1206 ms 131940 KB Output is correct
28 Correct 1129 ms 132316 KB Output is correct
29 Correct 1332 ms 132144 KB Output is correct
30 Correct 1252 ms 132176 KB Output is correct
31 Correct 30 ms 44876 KB Output is correct
32 Correct 75 ms 50720 KB Output is correct
33 Correct 439 ms 58800 KB Output is correct
34 Correct 1211 ms 123836 KB Output is correct
35 Correct 74 ms 47516 KB Output is correct
36 Correct 397 ms 58140 KB Output is correct
37 Correct 1154 ms 71344 KB Output is correct
38 Correct 380 ms 76256 KB Output is correct
39 Correct 531 ms 87024 KB Output is correct
40 Correct 847 ms 99968 KB Output is correct
41 Correct 960 ms 111084 KB Output is correct
42 Correct 1046 ms 121708 KB Output is correct
43 Correct 28 ms 44888 KB Output is correct
44 Correct 24 ms 44952 KB Output is correct
45 Correct 23 ms 44952 KB Output is correct
46 Correct 24 ms 44944 KB Output is correct
47 Correct 27 ms 44948 KB Output is correct
48 Correct 26 ms 44944 KB Output is correct
49 Correct 24 ms 44920 KB Output is correct
50 Correct 34 ms 44936 KB Output is correct
51 Correct 24 ms 44952 KB Output is correct
52 Correct 30 ms 44884 KB Output is correct
53 Correct 24 ms 44944 KB Output is correct
54 Correct 33 ms 45256 KB Output is correct
55 Correct 29 ms 45396 KB Output is correct
56 Correct 196 ms 64120 KB Output is correct
57 Correct 253 ms 73016 KB Output is correct
58 Correct 303 ms 72876 KB Output is correct
59 Correct 28 ms 44884 KB Output is correct
60 Correct 25 ms 44988 KB Output is correct
61 Correct 26 ms 44876 KB Output is correct
62 Correct 297 ms 84888 KB Output is correct
63 Correct 291 ms 84984 KB Output is correct
64 Correct 286 ms 85112 KB Output is correct
65 Correct 30 ms 45772 KB Output is correct
66 Correct 39 ms 46792 KB Output is correct
67 Correct 169 ms 70132 KB Output is correct
68 Correct 309 ms 83272 KB Output is correct
69 Correct 335 ms 95440 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct
17 Correct 1068 ms 137500 KB Output is correct
18 Correct 1150 ms 137040 KB Output is correct
19 Correct 1157 ms 124596 KB Output is correct
20 Correct 1124 ms 118396 KB Output is correct
21 Correct 917 ms 116980 KB Output is correct
22 Correct 29 ms 44884 KB Output is correct
23 Correct 113 ms 57296 KB Output is correct
24 Correct 127 ms 49976 KB Output is correct
25 Correct 519 ms 62680 KB Output is correct
26 Correct 1521 ms 75468 KB Output is correct
27 Correct 428 ms 83444 KB Output is correct
28 Correct 606 ms 93060 KB Output is correct
29 Correct 760 ms 103892 KB Output is correct
30 Correct 953 ms 112604 KB Output is correct
31 Correct 1140 ms 121764 KB Output is correct
32 Correct 429 ms 97592 KB Output is correct
33 Correct 315 ms 85892 KB Output is correct
34 Correct 30 ms 46112 KB Output is correct
35 Correct 32 ms 47004 KB Output is correct
36 Correct 214 ms 71012 KB Output is correct
37 Correct 280 ms 84288 KB Output is correct
38 Correct 384 ms 97212 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 44876 KB Output is correct
2 Correct 21 ms 44912 KB Output is correct
3 Correct 21 ms 44884 KB Output is correct
4 Correct 21 ms 44848 KB Output is correct
5 Correct 21 ms 44892 KB Output is correct
6 Correct 21 ms 44876 KB Output is correct
7 Correct 26 ms 44884 KB Output is correct
8 Correct 23 ms 44964 KB Output is correct
9 Correct 119 ms 59204 KB Output is correct
10 Correct 31 ms 46540 KB Output is correct
11 Correct 58 ms 52584 KB Output is correct
12 Correct 30 ms 47280 KB Output is correct
13 Correct 41 ms 49684 KB Output is correct
14 Correct 24 ms 45068 KB Output is correct
15 Correct 23 ms 45160 KB Output is correct
16 Correct 114 ms 59144 KB Output is correct
17 Correct 23 ms 44884 KB Output is correct
18 Correct 27 ms 44884 KB Output is correct
19 Correct 25 ms 44960 KB Output is correct
20 Correct 22 ms 44884 KB Output is correct
21 Correct 21 ms 44900 KB Output is correct
22 Correct 21 ms 44884 KB Output is correct
23 Correct 320 ms 87320 KB Output is correct
24 Correct 24 ms 44904 KB Output is correct
25 Correct 25 ms 45196 KB Output is correct
26 Correct 26 ms 45396 KB Output is correct
27 Correct 29 ms 45644 KB Output is correct
28 Correct 148 ms 61940 KB Output is correct
29 Correct 192 ms 70440 KB Output is correct
30 Correct 238 ms 78820 KB Output is correct
31 Correct 373 ms 87432 KB Output is correct
32 Correct 21 ms 44856 KB Output is correct
33 Correct 19 ms 44852 KB Output is correct
34 Correct 19 ms 44920 KB Output is correct
35 Correct 30 ms 44844 KB Output is correct
36 Correct 23 ms 44880 KB Output is correct
37 Correct 23 ms 44856 KB Output is correct
38 Correct 21 ms 44856 KB Output is correct
39 Correct 24 ms 44896 KB Output is correct
40 Correct 21 ms 44864 KB Output is correct
41 Correct 20 ms 44884 KB Output is correct
42 Correct 24 ms 44876 KB Output is correct
43 Correct 21 ms 45268 KB Output is correct
44 Correct 25 ms 45408 KB Output is correct
45 Correct 185 ms 63160 KB Output is correct
46 Correct 244 ms 71712 KB Output is correct
47 Correct 184 ms 71640 KB Output is correct
48 Correct 25 ms 44884 KB Output is correct
49 Correct 23 ms 44892 KB Output is correct
50 Correct 24 ms 44956 KB Output is correct
51 Correct 24 ms 44884 KB Output is correct
52 Correct 30 ms 44880 KB Output is correct
53 Correct 31 ms 44884 KB Output is correct
54 Correct 29 ms 44880 KB Output is correct
55 Correct 368 ms 86928 KB Output is correct
56 Correct 25 ms 44876 KB Output is correct
57 Correct 26 ms 45324 KB Output is correct
58 Correct 36 ms 46332 KB Output is correct
59 Correct 31 ms 46784 KB Output is correct
60 Correct 157 ms 65608 KB Output is correct
61 Correct 215 ms 74236 KB Output is correct
62 Correct 252 ms 79580 KB Output is correct
63 Correct 311 ms 86512 KB Output is correct
64 Correct 28 ms 44856 KB Output is correct
65 Correct 28 ms 44952 KB Output is correct
66 Correct 21 ms 44936 KB Output is correct
67 Correct 299 ms 83220 KB Output is correct
68 Correct 305 ms 83344 KB Output is correct
69 Correct 286 ms 83492 KB Output is correct
70 Correct 33 ms 45788 KB Output is correct
71 Correct 34 ms 46696 KB Output is correct
72 Correct 158 ms 69288 KB Output is correct
73 Correct 294 ms 82056 KB Output is correct
74 Correct 385 ms 93776 KB Output is correct
75 Correct 415 ms 95908 KB Output is correct
76 Correct 308 ms 84220 KB Output is correct
77 Correct 29 ms 46036 KB Output is correct
78 Correct 36 ms 46976 KB Output is correct
79 Correct 159 ms 70296 KB Output is correct
80 Correct 313 ms 82996 KB Output is correct
81 Correct 415 ms 95592 KB Output is correct
82 Correct 31 ms 44896 KB Output is correct
83 Correct 23 ms 44884 KB Output is correct
84 Correct 23 ms 44896 KB Output is correct
85 Correct 1055 ms 122084 KB Output is correct
86 Correct 1045 ms 121644 KB Output is correct
87 Correct 1127 ms 120692 KB Output is correct
88 Correct 870 ms 122556 KB Output is correct
89 Correct 1450 ms 70716 KB Output is correct
90 Correct 3406 ms 94056 KB Output is correct
91 Correct 2764 ms 93824 KB Output is correct
92 Correct 1206 ms 131940 KB Output is correct
93 Correct 1129 ms 132316 KB Output is correct
94 Correct 1332 ms 132144 KB Output is correct
95 Correct 1252 ms 132176 KB Output is correct
96 Correct 30 ms 44876 KB Output is correct
97 Correct 75 ms 50720 KB Output is correct
98 Correct 439 ms 58800 KB Output is correct
99 Correct 1211 ms 123836 KB Output is correct
100 Correct 74 ms 47516 KB Output is correct
101 Correct 397 ms 58140 KB Output is correct
102 Correct 1154 ms 71344 KB Output is correct
103 Correct 380 ms 76256 KB Output is correct
104 Correct 531 ms 87024 KB Output is correct
105 Correct 847 ms 99968 KB Output is correct
106 Correct 960 ms 111084 KB Output is correct
107 Correct 1046 ms 121708 KB Output is correct
108 Correct 28 ms 44888 KB Output is correct
109 Correct 24 ms 44952 KB Output is correct
110 Correct 23 ms 44952 KB Output is correct
111 Correct 24 ms 44944 KB Output is correct
112 Correct 27 ms 44948 KB Output is correct
113 Correct 26 ms 44944 KB Output is correct
114 Correct 24 ms 44920 KB Output is correct
115 Correct 34 ms 44936 KB Output is correct
116 Correct 24 ms 44952 KB Output is correct
117 Correct 30 ms 44884 KB Output is correct
118 Correct 24 ms 44944 KB Output is correct
119 Correct 33 ms 45256 KB Output is correct
120 Correct 29 ms 45396 KB Output is correct
121 Correct 196 ms 64120 KB Output is correct
122 Correct 253 ms 73016 KB Output is correct
123 Correct 303 ms 72876 KB Output is correct
124 Correct 28 ms 44884 KB Output is correct
125 Correct 25 ms 44988 KB Output is correct
126 Correct 26 ms 44876 KB Output is correct
127 Correct 297 ms 84888 KB Output is correct
128 Correct 291 ms 84984 KB Output is correct
129 Correct 286 ms 85112 KB Output is correct
130 Correct 30 ms 45772 KB Output is correct
131 Correct 39 ms 46792 KB Output is correct
132 Correct 169 ms 70132 KB Output is correct
133 Correct 309 ms 83272 KB Output is correct
134 Correct 335 ms 95440 KB Output is correct
135 Correct 1068 ms 137500 KB Output is correct
136 Correct 1150 ms 137040 KB Output is correct
137 Correct 1157 ms 124596 KB Output is correct
138 Correct 1124 ms 118396 KB Output is correct
139 Correct 917 ms 116980 KB Output is correct
140 Correct 29 ms 44884 KB Output is correct
141 Correct 113 ms 57296 KB Output is correct
142 Correct 127 ms 49976 KB Output is correct
143 Correct 519 ms 62680 KB Output is correct
144 Correct 1521 ms 75468 KB Output is correct
145 Correct 428 ms 83444 KB Output is correct
146 Correct 606 ms 93060 KB Output is correct
147 Correct 760 ms 103892 KB Output is correct
148 Correct 953 ms 112604 KB Output is correct
149 Correct 1140 ms 121764 KB Output is correct
150 Correct 429 ms 97592 KB Output is correct
151 Correct 315 ms 85892 KB Output is correct
152 Correct 30 ms 46112 KB Output is correct
153 Correct 32 ms 47004 KB Output is correct
154 Correct 214 ms 71012 KB Output is correct
155 Correct 280 ms 84288 KB Output is correct
156 Correct 384 ms 97212 KB Output is correct
157 Correct 24 ms 44912 KB Output is correct
158 Correct 25 ms 44884 KB Output is correct
159 Correct 28 ms 44884 KB Output is correct
160 Correct 25 ms 44892 KB Output is correct
161 Execution timed out 3542 ms 114548 KB Time limit exceeded
162 Halted 0 ms 0 KB -