oj.uz

Submission #824915

# Submission time Handle Problem Language Result Execution time Memory
824915 2023-08-14T11:51:43 Z andrei_boaca Fountain Parks (IOI21_parks) C++17
70 / 100
 2554 ms 135792 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<=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();
            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 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct
17 Correct 22 ms 44868 KB Output is correct
18 Correct 25 ms 44884 KB Output is correct
19 Correct 20 ms 44864 KB Output is correct
20 Correct 22 ms 44952 KB Output is correct
21 Correct 23 ms 44844 KB Output is correct
22 Correct 22 ms 44924 KB Output is correct
23 Correct 404 ms 87304 KB Output is correct
24 Correct 20 ms 44852 KB Output is correct
25 Correct 25 ms 45160 KB Output is correct
26 Correct 29 ms 45396 KB Output is correct
27 Correct 26 ms 45536 KB Output is correct
28 Correct 132 ms 61964 KB Output is correct
29 Correct 205 ms 70332 KB Output is correct
30 Correct 275 ms 78820 KB Output is correct
31 Correct 359 ms 87384 KB Output is correct
32 Correct 25 ms 44876 KB Output is correct
33 Correct 23 ms 44888 KB Output is correct
34 Correct 24 ms 44916 KB Output is correct
35 Correct 21 ms 44884 KB Output is correct
36 Correct 24 ms 44972 KB Output is correct
37 Correct 20 ms 44884 KB Output is correct
38 Correct 24 ms 44952 KB Output is correct
39 Correct 20 ms 44884 KB Output is correct
40 Correct 22 ms 44868 KB Output is correct
41 Correct 23 ms 44912 KB Output is correct
42 Correct 22 ms 44860 KB Output is correct
43 Correct 23 ms 45268 KB Output is correct
44 Correct 25 ms 45324 KB Output is correct
45 Correct 153 ms 63248 KB Output is correct
46 Correct 196 ms 71784 KB Output is correct
47 Correct 239 ms 71604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct
17 Correct 22 ms 44868 KB Output is correct
18 Correct 25 ms 44884 KB Output is correct
19 Correct 20 ms 44864 KB Output is correct
20 Correct 22 ms 44952 KB Output is correct
21 Correct 23 ms 44844 KB Output is correct
22 Correct 22 ms 44924 KB Output is correct
23 Correct 404 ms 87304 KB Output is correct
24 Correct 20 ms 44852 KB Output is correct
25 Correct 25 ms 45160 KB Output is correct
26 Correct 29 ms 45396 KB Output is correct
27 Correct 26 ms 45536 KB Output is correct
28 Correct 132 ms 61964 KB Output is correct
29 Correct 205 ms 70332 KB Output is correct
30 Correct 275 ms 78820 KB Output is correct
31 Correct 359 ms 87384 KB Output is correct
32 Correct 25 ms 44876 KB Output is correct
33 Correct 23 ms 44888 KB Output is correct
34 Correct 24 ms 44916 KB Output is correct
35 Correct 21 ms 44884 KB Output is correct
36 Correct 24 ms 44972 KB Output is correct
37 Correct 20 ms 44884 KB Output is correct
38 Correct 24 ms 44952 KB Output is correct
39 Correct 20 ms 44884 KB Output is correct
40 Correct 22 ms 44868 KB Output is correct
41 Correct 23 ms 44912 KB Output is correct
42 Correct 22 ms 44860 KB Output is correct
43 Correct 23 ms 45268 KB Output is correct
44 Correct 25 ms 45324 KB Output is correct
45 Correct 153 ms 63248 KB Output is correct
46 Correct 196 ms 71784 KB Output is correct
47 Correct 239 ms 71604 KB Output is correct
48 Correct 23 ms 44936 KB Output is correct
49 Correct 25 ms 44896 KB Output is correct
50 Correct 20 ms 44892 KB Output is correct
51 Correct 25 ms 44980 KB Output is correct
52 Correct 26 ms 44916 KB Output is correct
53 Correct 26 ms 44884 KB Output is correct
54 Correct 23 ms 44884 KB Output is correct
55 Correct 342 ms 86952 KB Output is correct
56 Correct 23 ms 44884 KB Output is correct
57 Correct 26 ms 45324 KB Output is correct
58 Correct 32 ms 46348 KB Output is correct
59 Correct 37 ms 46768 KB Output is correct
60 Correct 152 ms 65604 KB Output is correct
61 Correct 210 ms 74216 KB Output is correct
62 Correct 266 ms 79612 KB Output is correct
63 Correct 378 ms 86508 KB Output is correct
64 Correct 21 ms 44884 KB Output is correct
65 Correct 20 ms 44904 KB Output is correct
66 Correct 33 ms 44948 KB Output is correct
67 Correct 288 ms 83220 KB Output is correct
68 Correct 327 ms 83316 KB Output is correct
69 Correct 334 ms 83700 KB Output is correct
70 Correct 32 ms 45848 KB Output is correct
71 Correct 40 ms 46720 KB Output is correct
72 Correct 202 ms 69708 KB Output is correct
73 Correct 306 ms 82308 KB Output is correct
74 Correct 444 ms 94132 KB Output is correct
75 Correct 420 ms 96344 KB Output is correct
76 Correct 351 ms 85004 KB Output is correct
77 Correct 29 ms 46036 KB Output is correct
78 Correct 33 ms 47056 KB Output is correct
79 Correct 194 ms 71076 KB Output is correct
80 Correct 295 ms 83752 KB Output is correct
81 Correct 391 ms 96596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct
17 Correct 32 ms 44896 KB Output is correct
18 Correct 23 ms 44896 KB Output is correct
19 Correct 24 ms 44956 KB Output is correct
20 Correct 1189 ms 123756 KB Output is correct
21 Correct 1276 ms 123348 KB Output is correct
22 Correct 1117 ms 122568 KB Output is correct
23 Correct 984 ms 123820 KB Output is correct
24 Correct 916 ms 71812 KB Output is correct
25 Correct 2013 ms 89280 KB Output is correct
26 Correct 1714 ms 88076 KB Output is correct
27 Correct 1236 ms 130588 KB Output is correct
28 Correct 1219 ms 130744 KB Output is correct
29 Correct 1249 ms 130448 KB Output is correct
30 Correct 1349 ms 131012 KB Output is correct
31 Correct 29 ms 44944 KB Output is correct
32 Correct 72 ms 50760 KB Output is correct
33 Correct 282 ms 58156 KB Output is correct
34 Correct 1157 ms 121808 KB Output is correct
35 Correct 55 ms 47264 KB Output is correct
36 Correct 341 ms 56540 KB Output is correct
37 Correct 822 ms 68052 KB Output is correct
38 Correct 412 ms 76208 KB Output is correct
39 Correct 561 ms 86832 KB Output is correct
40 Correct 748 ms 99124 KB Output is correct
41 Correct 877 ms 110304 KB Output is correct
42 Correct 1270 ms 121952 KB Output is correct
43 Correct 29 ms 44924 KB Output is correct
44 Correct 33 ms 44868 KB Output is correct
45 Correct 25 ms 44884 KB Output is correct
46 Correct 25 ms 44872 KB Output is correct
47 Correct 35 ms 44936 KB Output is correct
48 Correct 24 ms 44884 KB Output is correct
49 Correct 23 ms 44884 KB Output is correct
50 Correct 28 ms 44928 KB Output is correct
51 Correct 22 ms 44884 KB Output is correct
52 Correct 35 ms 44876 KB Output is correct
53 Correct 30 ms 44884 KB Output is correct
54 Correct 30 ms 45176 KB Output is correct
55 Correct 31 ms 45388 KB Output is correct
56 Correct 134 ms 64060 KB Output is correct
57 Correct 263 ms 72916 KB Output is correct
58 Correct 225 ms 72832 KB Output is correct
59 Correct 24 ms 44884 KB Output is correct
60 Correct 23 ms 44884 KB Output is correct
61 Correct 28 ms 44876 KB Output is correct
62 Correct 305 ms 84876 KB Output is correct
63 Correct 309 ms 84988 KB Output is correct
64 Correct 351 ms 85112 KB Output is correct
65 Correct 29 ms 45836 KB Output is correct
66 Correct 32 ms 46740 KB Output is correct
67 Correct 181 ms 70096 KB Output is correct
68 Correct 292 ms 83264 KB Output is correct
69 Correct 376 ms 95160 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct
17 Correct 1094 ms 135792 KB Output is correct
18 Correct 1122 ms 135116 KB Output is correct
19 Correct 1027 ms 122404 KB Output is correct
20 Correct 1035 ms 116932 KB Output is correct
21 Correct 963 ms 115564 KB Output is correct
22 Correct 24 ms 44868 KB Output is correct
23 Correct 111 ms 56900 KB Output is correct
24 Correct 101 ms 49188 KB Output is correct
25 Correct 354 ms 59720 KB Output is correct
26 Correct 882 ms 70620 KB Output is correct
27 Correct 460 ms 82188 KB Output is correct
28 Correct 622 ms 91392 KB Output is correct
29 Correct 713 ms 101840 KB Output is correct
30 Correct 954 ms 110424 KB Output is correct
31 Correct 1120 ms 119664 KB Output is correct
32 Correct 352 ms 95796 KB Output is correct
33 Correct 286 ms 84216 KB Output is correct
34 Correct 29 ms 46008 KB Output is correct
35 Correct 33 ms 46932 KB Output is correct
36 Correct 184 ms 70236 KB Output is correct
37 Correct 282 ms 82936 KB Output is correct
38 Correct 376 ms 95640 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44884 KB Output is correct
2 Correct 24 ms 44892 KB Output is correct
3 Correct 24 ms 44884 KB Output is correct
4 Correct 29 ms 44912 KB Output is correct
5 Correct 20 ms 44884 KB Output is correct
6 Correct 24 ms 44852 KB Output is correct
7 Correct 21 ms 44904 KB Output is correct
8 Correct 25 ms 44884 KB Output is correct
9 Correct 105 ms 59220 KB Output is correct
10 Correct 36 ms 46548 KB Output is correct
11 Correct 54 ms 52636 KB Output is correct
12 Correct 39 ms 47232 KB Output is correct
13 Correct 40 ms 49680 KB Output is correct
14 Correct 24 ms 45012 KB Output is correct
15 Correct 19 ms 45140 KB Output is correct
16 Correct 108 ms 59148 KB Output is correct
17 Correct 22 ms 44868 KB Output is correct
18 Correct 25 ms 44884 KB Output is correct
19 Correct 20 ms 44864 KB Output is correct
20 Correct 22 ms 44952 KB Output is correct
21 Correct 23 ms 44844 KB Output is correct
22 Correct 22 ms 44924 KB Output is correct
23 Correct 404 ms 87304 KB Output is correct
24 Correct 20 ms 44852 KB Output is correct
25 Correct 25 ms 45160 KB Output is correct
26 Correct 29 ms 45396 KB Output is correct
27 Correct 26 ms 45536 KB Output is correct
28 Correct 132 ms 61964 KB Output is correct
29 Correct 205 ms 70332 KB Output is correct
30 Correct 275 ms 78820 KB Output is correct
31 Correct 359 ms 87384 KB Output is correct
32 Correct 25 ms 44876 KB Output is correct
33 Correct 23 ms 44888 KB Output is correct
34 Correct 24 ms 44916 KB Output is correct
35 Correct 21 ms 44884 KB Output is correct
36 Correct 24 ms 44972 KB Output is correct
37 Correct 20 ms 44884 KB Output is correct
38 Correct 24 ms 44952 KB Output is correct
39 Correct 20 ms 44884 KB Output is correct
40 Correct 22 ms 44868 KB Output is correct
41 Correct 23 ms 44912 KB Output is correct
42 Correct 22 ms 44860 KB Output is correct
43 Correct 23 ms 45268 KB Output is correct
44 Correct 25 ms 45324 KB Output is correct
45 Correct 153 ms 63248 KB Output is correct
46 Correct 196 ms 71784 KB Output is correct
47 Correct 239 ms 71604 KB Output is correct
48 Correct 23 ms 44936 KB Output is correct
49 Correct 25 ms 44896 KB Output is correct
50 Correct 20 ms 44892 KB Output is correct
51 Correct 25 ms 44980 KB Output is correct
52 Correct 26 ms 44916 KB Output is correct
53 Correct 26 ms 44884 KB Output is correct
54 Correct 23 ms 44884 KB Output is correct
55 Correct 342 ms 86952 KB Output is correct
56 Correct 23 ms 44884 KB Output is correct
57 Correct 26 ms 45324 KB Output is correct
58 Correct 32 ms 46348 KB Output is correct
59 Correct 37 ms 46768 KB Output is correct
60 Correct 152 ms 65604 KB Output is correct
61 Correct 210 ms 74216 KB Output is correct
62 Correct 266 ms 79612 KB Output is correct
63 Correct 378 ms 86508 KB Output is correct
64 Correct 21 ms 44884 KB Output is correct
65 Correct 20 ms 44904 KB Output is correct
66 Correct 33 ms 44948 KB Output is correct
67 Correct 288 ms 83220 KB Output is correct
68 Correct 327 ms 83316 KB Output is correct
69 Correct 334 ms 83700 KB Output is correct
70 Correct 32 ms 45848 KB Output is correct
71 Correct 40 ms 46720 KB Output is correct
72 Correct 202 ms 69708 KB Output is correct
73 Correct 306 ms 82308 KB Output is correct
74 Correct 444 ms 94132 KB Output is correct
75 Correct 420 ms 96344 KB Output is correct
76 Correct 351 ms 85004 KB Output is correct
77 Correct 29 ms 46036 KB Output is correct
78 Correct 33 ms 47056 KB Output is correct
79 Correct 194 ms 71076 KB Output is correct
80 Correct 295 ms 83752 KB Output is correct
81 Correct 391 ms 96596 KB Output is correct
82 Correct 32 ms 44896 KB Output is correct
83 Correct 23 ms 44896 KB Output is correct
84 Correct 24 ms 44956 KB Output is correct
85 Correct 1189 ms 123756 KB Output is correct
86 Correct 1276 ms 123348 KB Output is correct
87 Correct 1117 ms 122568 KB Output is correct
88 Correct 984 ms 123820 KB Output is correct
89 Correct 916 ms 71812 KB Output is correct
90 Correct 2013 ms 89280 KB Output is correct
91 Correct 1714 ms 88076 KB Output is correct
92 Correct 1236 ms 130588 KB Output is correct
93 Correct 1219 ms 130744 KB Output is correct
94 Correct 1249 ms 130448 KB Output is correct
95 Correct 1349 ms 131012 KB Output is correct
96 Correct 29 ms 44944 KB Output is correct
97 Correct 72 ms 50760 KB Output is correct
98 Correct 282 ms 58156 KB Output is correct
99 Correct 1157 ms 121808 KB Output is correct
100 Correct 55 ms 47264 KB Output is correct
101 Correct 341 ms 56540 KB Output is correct
102 Correct 822 ms 68052 KB Output is correct
103 Correct 412 ms 76208 KB Output is correct
104 Correct 561 ms 86832 KB Output is correct
105 Correct 748 ms 99124 KB Output is correct
106 Correct 877 ms 110304 KB Output is correct
107 Correct 1270 ms 121952 KB Output is correct
108 Correct 29 ms 44924 KB Output is correct
109 Correct 33 ms 44868 KB Output is correct
110 Correct 25 ms 44884 KB Output is correct
111 Correct 25 ms 44872 KB Output is correct
112 Correct 35 ms 44936 KB Output is correct
113 Correct 24 ms 44884 KB Output is correct
114 Correct 23 ms 44884 KB Output is correct
115 Correct 28 ms 44928 KB Output is correct
116 Correct 22 ms 44884 KB Output is correct
117 Correct 35 ms 44876 KB Output is correct
118 Correct 30 ms 44884 KB Output is correct
119 Correct 30 ms 45176 KB Output is correct
120 Correct 31 ms 45388 KB Output is correct
121 Correct 134 ms 64060 KB Output is correct
122 Correct 263 ms 72916 KB Output is correct
123 Correct 225 ms 72832 KB Output is correct
124 Correct 24 ms 44884 KB Output is correct
125 Correct 23 ms 44884 KB Output is correct
126 Correct 28 ms 44876 KB Output is correct
127 Correct 305 ms 84876 KB Output is correct
128 Correct 309 ms 84988 KB Output is correct
129 Correct 351 ms 85112 KB Output is correct
130 Correct 29 ms 45836 KB Output is correct
131 Correct 32 ms 46740 KB Output is correct
132 Correct 181 ms 70096 KB Output is correct
133 Correct 292 ms 83264 KB Output is correct
134 Correct 376 ms 95160 KB Output is correct
135 Correct 1094 ms 135792 KB Output is correct
136 Correct 1122 ms 135116 KB Output is correct
137 Correct 1027 ms 122404 KB Output is correct
138 Correct 1035 ms 116932 KB Output is correct
139 Correct 963 ms 115564 KB Output is correct
140 Correct 24 ms 44868 KB Output is correct
141 Correct 111 ms 56900 KB Output is correct
142 Correct 101 ms 49188 KB Output is correct
143 Correct 354 ms 59720 KB Output is correct
144 Correct 882 ms 70620 KB Output is correct
145 Correct 460 ms 82188 KB Output is correct
146 Correct 622 ms 91392 KB Output is correct
147 Correct 713 ms 101840 KB Output is correct
148 Correct 954 ms 110424 KB Output is correct
149 Correct 1120 ms 119664 KB Output is correct
150 Correct 352 ms 95796 KB Output is correct
151 Correct 286 ms 84216 KB Output is correct
152 Correct 29 ms 46008 KB Output is correct
153 Correct 33 ms 46932 KB Output is correct
154 Correct 184 ms 70236 KB Output is correct
155 Correct 282 ms 82936 KB Output is correct
156 Correct 376 ms 95640 KB Output is correct
157 Correct 24 ms 44884 KB Output is correct
158 Correct 23 ms 44964 KB Output is correct
159 Correct 24 ms 44884 KB Output is correct
160 Correct 24 ms 44904 KB Output is correct
161 Incorrect 2554 ms 111092 KB Solution announced impossible, but it is possible.
162 Halted 0 ms 0 KB -