oj.uz

Submission #824919

# Submission time Handle Problem Language Result Execution time Memory
824919 2023-08-14T11:56:46 Z andrei_boaca Fountain Parks (IOI21_parks) C++17
70 / 100
 3113 ms 163664 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[2000005];
int l[2000005],r[2000005];
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<=2)
    {
        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();
            l[i+1]=0;
            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);
                r[nrm]=0;

                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);
                r[nrm]=0;
            }
            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);
                r[nrm]=0;

                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);
                r[nrm]=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:382: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]
  382 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:384: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]
  384 |             for(int i=1;i<=edges.size();i++)
      |                         ~^~~~~~~~~~~~~~
parks.cpp:388: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]
  388 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~
parks.cpp:393: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]
  393 |         for(int i=1;i<=edges.size();i++)
      |                     ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct
17 Correct 32 ms 73044 KB Output is correct
18 Correct 36 ms 73104 KB Output is correct
19 Correct 44 ms 73020 KB Output is correct
20 Correct 37 ms 73120 KB Output is correct
21 Correct 42 ms 73036 KB Output is correct
22 Correct 33 ms 73140 KB Output is correct
23 Correct 409 ms 117140 KB Output is correct
24 Correct 35 ms 73088 KB Output is correct
25 Correct 38 ms 73400 KB Output is correct
26 Correct 35 ms 73704 KB Output is correct
27 Correct 48 ms 73820 KB Output is correct
28 Correct 157 ms 90736 KB Output is correct
29 Correct 235 ms 99536 KB Output is correct
30 Correct 382 ms 108464 KB Output is correct
31 Correct 384 ms 117172 KB Output is correct
32 Correct 36 ms 73044 KB Output is correct
33 Correct 42 ms 73036 KB Output is correct
34 Correct 37 ms 73044 KB Output is correct
35 Correct 36 ms 73112 KB Output is correct
36 Correct 35 ms 73112 KB Output is correct
37 Correct 34 ms 73096 KB Output is correct
38 Correct 36 ms 73116 KB Output is correct
39 Correct 35 ms 73132 KB Output is correct
40 Correct 37 ms 73060 KB Output is correct
41 Correct 38 ms 73124 KB Output is correct
42 Correct 39 ms 73020 KB Output is correct
43 Correct 37 ms 73412 KB Output is correct
44 Correct 36 ms 73520 KB Output is correct
45 Correct 154 ms 92280 KB Output is correct
46 Correct 239 ms 101172 KB Output is correct
47 Correct 268 ms 101100 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct
17 Correct 32 ms 73044 KB Output is correct
18 Correct 36 ms 73104 KB Output is correct
19 Correct 44 ms 73020 KB Output is correct
20 Correct 37 ms 73120 KB Output is correct
21 Correct 42 ms 73036 KB Output is correct
22 Correct 33 ms 73140 KB Output is correct
23 Correct 409 ms 117140 KB Output is correct
24 Correct 35 ms 73088 KB Output is correct
25 Correct 38 ms 73400 KB Output is correct
26 Correct 35 ms 73704 KB Output is correct
27 Correct 48 ms 73820 KB Output is correct
28 Correct 157 ms 90736 KB Output is correct
29 Correct 235 ms 99536 KB Output is correct
30 Correct 382 ms 108464 KB Output is correct
31 Correct 384 ms 117172 KB Output is correct
32 Correct 36 ms 73044 KB Output is correct
33 Correct 42 ms 73036 KB Output is correct
34 Correct 37 ms 73044 KB Output is correct
35 Correct 36 ms 73112 KB Output is correct
36 Correct 35 ms 73112 KB Output is correct
37 Correct 34 ms 73096 KB Output is correct
38 Correct 36 ms 73116 KB Output is correct
39 Correct 35 ms 73132 KB Output is correct
40 Correct 37 ms 73060 KB Output is correct
41 Correct 38 ms 73124 KB Output is correct
42 Correct 39 ms 73020 KB Output is correct
43 Correct 37 ms 73412 KB Output is correct
44 Correct 36 ms 73520 KB Output is correct
45 Correct 154 ms 92280 KB Output is correct
46 Correct 239 ms 101172 KB Output is correct
47 Correct 268 ms 101100 KB Output is correct
48 Correct 43 ms 73056 KB Output is correct
49 Correct 35 ms 73064 KB Output is correct
50 Correct 35 ms 73056 KB Output is correct
51 Correct 36 ms 73096 KB Output is correct
52 Correct 36 ms 73144 KB Output is correct
53 Correct 34 ms 73088 KB Output is correct
54 Correct 36 ms 73080 KB Output is correct
55 Correct 327 ms 116696 KB Output is correct
56 Correct 43 ms 73156 KB Output is correct
57 Correct 37 ms 73540 KB Output is correct
58 Correct 40 ms 74580 KB Output is correct
59 Correct 41 ms 75076 KB Output is correct
60 Correct 147 ms 94484 KB Output is correct
61 Correct 207 ms 103412 KB Output is correct
62 Correct 255 ms 109220 KB Output is correct
63 Correct 294 ms 116348 KB Output is correct
64 Correct 37 ms 73148 KB Output is correct
65 Correct 37 ms 73064 KB Output is correct
66 Correct 36 ms 73136 KB Output is correct
67 Correct 291 ms 113036 KB Output is correct
68 Correct 276 ms 113096 KB Output is correct
69 Correct 276 ms 113300 KB Output is correct
70 Correct 51 ms 74056 KB Output is correct
71 Correct 44 ms 74880 KB Output is correct
72 Correct 170 ms 98316 KB Output is correct
73 Correct 273 ms 111440 KB Output is correct
74 Correct 378 ms 123612 KB Output is correct
75 Correct 383 ms 125688 KB Output is correct
76 Correct 299 ms 114068 KB Output is correct
77 Correct 40 ms 74324 KB Output is correct
78 Correct 44 ms 75172 KB Output is correct
79 Correct 183 ms 99176 KB Output is correct
80 Correct 282 ms 112476 KB Output is correct
81 Correct 403 ms 125440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct
17 Correct 35 ms 73044 KB Output is correct
18 Correct 42 ms 73044 KB Output is correct
19 Correct 36 ms 73136 KB Output is correct
20 Correct 1027 ms 152396 KB Output is correct
21 Correct 1127 ms 152036 KB Output is correct
22 Correct 1056 ms 151076 KB Output is correct
23 Correct 905 ms 152044 KB Output is correct
24 Correct 777 ms 100092 KB Output is correct
25 Correct 1638 ms 117456 KB Output is correct
26 Correct 1476 ms 117012 KB Output is correct
27 Correct 1106 ms 160088 KB Output is correct
28 Correct 1044 ms 160460 KB Output is correct
29 Correct 1198 ms 160072 KB Output is correct
30 Correct 1288 ms 160264 KB Output is correct
31 Correct 46 ms 73100 KB Output is correct
32 Correct 72 ms 78916 KB Output is correct
33 Correct 283 ms 86936 KB Output is correct
34 Correct 983 ms 152036 KB Output is correct
35 Correct 66 ms 75364 KB Output is correct
36 Correct 248 ms 84888 KB Output is correct
37 Correct 583 ms 96372 KB Output is correct
38 Correct 330 ms 104468 KB Output is correct
39 Correct 478 ms 115180 KB Output is correct
40 Correct 697 ms 128180 KB Output is correct
41 Correct 828 ms 139300 KB Output is correct
42 Correct 1064 ms 149972 KB Output is correct
43 Correct 41 ms 73124 KB Output is correct
44 Correct 36 ms 73112 KB Output is correct
45 Correct 37 ms 73108 KB Output is correct
46 Correct 36 ms 73040 KB Output is correct
47 Correct 37 ms 73028 KB Output is correct
48 Correct 36 ms 73044 KB Output is correct
49 Correct 37 ms 73132 KB Output is correct
50 Correct 40 ms 73036 KB Output is correct
51 Correct 38 ms 73112 KB Output is correct
52 Correct 36 ms 73048 KB Output is correct
53 Correct 40 ms 73044 KB Output is correct
54 Correct 38 ms 73368 KB Output is correct
55 Correct 41 ms 73588 KB Output is correct
56 Correct 184 ms 91588 KB Output is correct
57 Correct 232 ms 100140 KB Output is correct
58 Correct 231 ms 100104 KB Output is correct
59 Correct 33 ms 73096 KB Output is correct
60 Correct 38 ms 73164 KB Output is correct
61 Correct 44 ms 73152 KB Output is correct
62 Correct 298 ms 111620 KB Output is correct
63 Correct 329 ms 111436 KB Output is correct
64 Correct 302 ms 111664 KB Output is correct
65 Correct 40 ms 74032 KB Output is correct
66 Correct 45 ms 74860 KB Output is correct
67 Correct 189 ms 97448 KB Output is correct
68 Correct 317 ms 110168 KB Output is correct
69 Correct 430 ms 121988 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct
17 Correct 1106 ms 163664 KB Output is correct
18 Correct 1111 ms 163068 KB Output is correct
19 Correct 1144 ms 150512 KB Output is correct
20 Correct 1177 ms 145136 KB Output is correct
21 Correct 994 ms 143644 KB Output is correct
22 Correct 37 ms 73040 KB Output is correct
23 Correct 143 ms 84996 KB Output is correct
24 Correct 105 ms 77368 KB Output is correct
25 Correct 480 ms 87932 KB Output is correct
26 Correct 885 ms 98668 KB Output is correct
27 Correct 524 ms 110348 KB Output is correct
28 Correct 578 ms 119424 KB Output is correct
29 Correct 707 ms 130112 KB Output is correct
30 Correct 856 ms 138680 KB Output is correct
31 Correct 1039 ms 147984 KB Output is correct
32 Correct 417 ms 124192 KB Output is correct
33 Correct 272 ms 112424 KB Output is correct
34 Correct 43 ms 74196 KB Output is correct
35 Correct 47 ms 75192 KB Output is correct
36 Correct 178 ms 98380 KB Output is correct
37 Correct 313 ms 111120 KB Output is correct
38 Correct 406 ms 123812 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 73048 KB Output is correct
2 Correct 34 ms 73052 KB Output is correct
3 Correct 36 ms 73020 KB Output is correct
4 Correct 36 ms 73004 KB Output is correct
5 Correct 33 ms 73044 KB Output is correct
6 Correct 33 ms 73036 KB Output is correct
7 Correct 33 ms 73120 KB Output is correct
8 Correct 33 ms 73124 KB Output is correct
9 Correct 132 ms 88112 KB Output is correct
10 Correct 39 ms 74836 KB Output is correct
11 Correct 68 ms 81272 KB Output is correct
12 Correct 52 ms 75596 KB Output is correct
13 Correct 49 ms 78308 KB Output is correct
14 Correct 32 ms 73184 KB Output is correct
15 Correct 35 ms 73340 KB Output is correct
16 Correct 138 ms 88148 KB Output is correct
17 Correct 32 ms 73044 KB Output is correct
18 Correct 36 ms 73104 KB Output is correct
19 Correct 44 ms 73020 KB Output is correct
20 Correct 37 ms 73120 KB Output is correct
21 Correct 42 ms 73036 KB Output is correct
22 Correct 33 ms 73140 KB Output is correct
23 Correct 409 ms 117140 KB Output is correct
24 Correct 35 ms 73088 KB Output is correct
25 Correct 38 ms 73400 KB Output is correct
26 Correct 35 ms 73704 KB Output is correct
27 Correct 48 ms 73820 KB Output is correct
28 Correct 157 ms 90736 KB Output is correct
29 Correct 235 ms 99536 KB Output is correct
30 Correct 382 ms 108464 KB Output is correct
31 Correct 384 ms 117172 KB Output is correct
32 Correct 36 ms 73044 KB Output is correct
33 Correct 42 ms 73036 KB Output is correct
34 Correct 37 ms 73044 KB Output is correct
35 Correct 36 ms 73112 KB Output is correct
36 Correct 35 ms 73112 KB Output is correct
37 Correct 34 ms 73096 KB Output is correct
38 Correct 36 ms 73116 KB Output is correct
39 Correct 35 ms 73132 KB Output is correct
40 Correct 37 ms 73060 KB Output is correct
41 Correct 38 ms 73124 KB Output is correct
42 Correct 39 ms 73020 KB Output is correct
43 Correct 37 ms 73412 KB Output is correct
44 Correct 36 ms 73520 KB Output is correct
45 Correct 154 ms 92280 KB Output is correct
46 Correct 239 ms 101172 KB Output is correct
47 Correct 268 ms 101100 KB Output is correct
48 Correct 43 ms 73056 KB Output is correct
49 Correct 35 ms 73064 KB Output is correct
50 Correct 35 ms 73056 KB Output is correct
51 Correct 36 ms 73096 KB Output is correct
52 Correct 36 ms 73144 KB Output is correct
53 Correct 34 ms 73088 KB Output is correct
54 Correct 36 ms 73080 KB Output is correct
55 Correct 327 ms 116696 KB Output is correct
56 Correct 43 ms 73156 KB Output is correct
57 Correct 37 ms 73540 KB Output is correct
58 Correct 40 ms 74580 KB Output is correct
59 Correct 41 ms 75076 KB Output is correct
60 Correct 147 ms 94484 KB Output is correct
61 Correct 207 ms 103412 KB Output is correct
62 Correct 255 ms 109220 KB Output is correct
63 Correct 294 ms 116348 KB Output is correct
64 Correct 37 ms 73148 KB Output is correct
65 Correct 37 ms 73064 KB Output is correct
66 Correct 36 ms 73136 KB Output is correct
67 Correct 291 ms 113036 KB Output is correct
68 Correct 276 ms 113096 KB Output is correct
69 Correct 276 ms 113300 KB Output is correct
70 Correct 51 ms 74056 KB Output is correct
71 Correct 44 ms 74880 KB Output is correct
72 Correct 170 ms 98316 KB Output is correct
73 Correct 273 ms 111440 KB Output is correct
74 Correct 378 ms 123612 KB Output is correct
75 Correct 383 ms 125688 KB Output is correct
76 Correct 299 ms 114068 KB Output is correct
77 Correct 40 ms 74324 KB Output is correct
78 Correct 44 ms 75172 KB Output is correct
79 Correct 183 ms 99176 KB Output is correct
80 Correct 282 ms 112476 KB Output is correct
81 Correct 403 ms 125440 KB Output is correct
82 Correct 35 ms 73044 KB Output is correct
83 Correct 42 ms 73044 KB Output is correct
84 Correct 36 ms 73136 KB Output is correct
85 Correct 1027 ms 152396 KB Output is correct
86 Correct 1127 ms 152036 KB Output is correct
87 Correct 1056 ms 151076 KB Output is correct
88 Correct 905 ms 152044 KB Output is correct
89 Correct 777 ms 100092 KB Output is correct
90 Correct 1638 ms 117456 KB Output is correct
91 Correct 1476 ms 117012 KB Output is correct
92 Correct 1106 ms 160088 KB Output is correct
93 Correct 1044 ms 160460 KB Output is correct
94 Correct 1198 ms 160072 KB Output is correct
95 Correct 1288 ms 160264 KB Output is correct
96 Correct 46 ms 73100 KB Output is correct
97 Correct 72 ms 78916 KB Output is correct
98 Correct 283 ms 86936 KB Output is correct
99 Correct 983 ms 152036 KB Output is correct
100 Correct 66 ms 75364 KB Output is correct
101 Correct 248 ms 84888 KB Output is correct
102 Correct 583 ms 96372 KB Output is correct
103 Correct 330 ms 104468 KB Output is correct
104 Correct 478 ms 115180 KB Output is correct
105 Correct 697 ms 128180 KB Output is correct
106 Correct 828 ms 139300 KB Output is correct
107 Correct 1064 ms 149972 KB Output is correct
108 Correct 41 ms 73124 KB Output is correct
109 Correct 36 ms 73112 KB Output is correct
110 Correct 37 ms 73108 KB Output is correct
111 Correct 36 ms 73040 KB Output is correct
112 Correct 37 ms 73028 KB Output is correct
113 Correct 36 ms 73044 KB Output is correct
114 Correct 37 ms 73132 KB Output is correct
115 Correct 40 ms 73036 KB Output is correct
116 Correct 38 ms 73112 KB Output is correct
117 Correct 36 ms 73048 KB Output is correct
118 Correct 40 ms 73044 KB Output is correct
119 Correct 38 ms 73368 KB Output is correct
120 Correct 41 ms 73588 KB Output is correct
121 Correct 184 ms 91588 KB Output is correct
122 Correct 232 ms 100140 KB Output is correct
123 Correct 231 ms 100104 KB Output is correct
124 Correct 33 ms 73096 KB Output is correct
125 Correct 38 ms 73164 KB Output is correct
126 Correct 44 ms 73152 KB Output is correct
127 Correct 298 ms 111620 KB Output is correct
128 Correct 329 ms 111436 KB Output is correct
129 Correct 302 ms 111664 KB Output is correct
130 Correct 40 ms 74032 KB Output is correct
131 Correct 45 ms 74860 KB Output is correct
132 Correct 189 ms 97448 KB Output is correct
133 Correct 317 ms 110168 KB Output is correct
134 Correct 430 ms 121988 KB Output is correct
135 Correct 1106 ms 163664 KB Output is correct
136 Correct 1111 ms 163068 KB Output is correct
137 Correct 1144 ms 150512 KB Output is correct
138 Correct 1177 ms 145136 KB Output is correct
139 Correct 994 ms 143644 KB Output is correct
140 Correct 37 ms 73040 KB Output is correct
141 Correct 143 ms 84996 KB Output is correct
142 Correct 105 ms 77368 KB Output is correct
143 Correct 480 ms 87932 KB Output is correct
144 Correct 885 ms 98668 KB Output is correct
145 Correct 524 ms 110348 KB Output is correct
146 Correct 578 ms 119424 KB Output is correct
147 Correct 707 ms 130112 KB Output is correct
148 Correct 856 ms 138680 KB Output is correct
149 Correct 1039 ms 147984 KB Output is correct
150 Correct 417 ms 124192 KB Output is correct
151 Correct 272 ms 112424 KB Output is correct
152 Correct 43 ms 74196 KB Output is correct
153 Correct 47 ms 75192 KB Output is correct
154 Correct 178 ms 98380 KB Output is correct
155 Correct 313 ms 111120 KB Output is correct
156 Correct 406 ms 123812 KB Output is correct
157 Correct 35 ms 73036 KB Output is correct
158 Correct 36 ms 73036 KB Output is correct
159 Correct 36 ms 73056 KB Output is correct
160 Correct 39 ms 73076 KB Output is correct
161 Incorrect 3113 ms 139388 KB Solution announced impossible, but it is possible.
162 Halted 0 ms 0 KB -