oj.uz

Submission #991194

# Submission time Handle Problem Language Result Execution time Memory
991194 2024-06-01T14:28:56 Z model_code Magic Show (APIO24_show) C++17
100 / 100
 140 ms 337020 KB 
#include"Alice.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace A{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u;
vector<pair<int,int>> p;
void link(ll x,ll y,ll z)
{
    ll i;
    for(i=y;i<=z;i++)
    {
        perm[i]=x;
        if(adj[x][i]==0)
        {
            adj[x][i]=1;
            adj[i][x]=1;
        }
    }
}
pair<ll,ll> f(ll x,ll y)
{
    //printf("%lld(%lld)\n",ll(x),y);
    c[x]=1;
    ll i,mn=100000,mx=0;
    pair<ll,ll> p;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        p=f(v[x][i],x);
        mn=min(mn,p.first);
        mx=max(mx,p.second);
    }
    if(h[x]<=1)
    {
        mn=min(mn,x);
        mx=max(mx,x);
    }
    return {mn,mx};
}
void Clear()
{
    ll i;
    for(i=1;i<=4991;i++)
    {
        v[i].clear();
        h[i]=0;
        b[i]=0;
        a[i]=0;
        c[i]=0;
        d[i]=0;
        perm[i]=0;
    }
    for(i=1;i<=4991;i++)
        for(j=1;j<=4991;j++)
    {
        adj[i][j]=0;
    }
}
vector<pair<int,int>> Alice()
{
    for(i=1;i<=4991;i++)
        adj[i][i]=1;
    k=setN(4991);
    i=1;
        while(k>0)
        {
           a[i]=k%mod;
           k/=mod;
           i++;
        }
        for(i=1;i<=31;i++)
        {
            x=i;
            j=1;
            while(x>0)
            {
                if(x&1)
                {
                    b[i]^=a[j];
                }
                x>>=1;
                j++;
            }
            b[i]++;
        }
        for(i=1;i<=31;i++)
        {
            if(i!=31)
            link(b[i],(i-1)*161+1,i*161);
            else
            {
                link(b[i],(i-1)*161+1,4991);
            }
        }
        n=4991;
        for(i=1;i<=n;i++)
        {
            if(c[i]==2)
                continue;
            x=i;
            y=0;
            while(1)
            {
                c[x]=1;
                y=x;
                x=perm[x];
                if(c[x]==2)
                    break;
                if(c[x]==1)
                {
                    if(x==y)
                        break;
                    adj[x][y]=0;
                    adj[y][x]=0;
                    break;
                }
            }
            x=i;
            while(1)
            {
                if(c[x]==2)
                    break;
                c[x]=2;
                x=perm[x];
            }
        }
        for(i=1;i<=n;i++)
        {
            c[i]=0;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {
                if(adj[i][j]==1)
                {
                    v[i].push_back(j);
                    v[j].push_back(i);
                    h[i]++;
                    h[j]++;
                    p.push_back({i,j});
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(c[i]==0)
            {
                u.push_back(f(i,0));
            }
        }
        for(i=0;i<u.size()-1;i++)
        {
            x=u[i].first;
            y=u[i+1].second;
            v[x].push_back(y);
            v[y].push_back(x);
            h[x]++;
            h[y]++;
            p.push_back({x,y});
        }
    return p;
}
};
vector<pair<int,int>> Alice()
{
    return A::Alice();
}

#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
namespace B{
const ll mod=4096;
ll n,i,j,k,l,r,x,y,z,w,s,t,a[1100000],b[1100000],adj[5500][5500],c[1100000],d[1100000],h[1100000],e,m,perm[1100000];
vector<ll> v[1100000];
vector<pair<ll,ll>> u,p;
void link(ll x,ll y,ll z)
{
    ll i;
    for(i=y;i<=z;i++)
    {
        perm[i]=x;
        if(adj[x][i]==0)
        {
            adj[x][i]=1;
            adj[i][x]=1;
        }
    }
}
pair<ll,ll> f(ll x,ll y)
{
    //printf("%lld(%lld)\n",ll(x),y);
    c[x]=1;
    ll i,mn=100000,mx=0;
    pair<ll,ll> p;
    for(i=0;i<h[x];i++)
    {
        if(v[x][i]==y)
            continue;
        p=f(v[x][i],x);
        mn=min(mn,p.first);
        mx=max(mx,p.second);
    }
    if(h[x]<=1)
    {
        mn=min(mn,x);
        mx=max(mx,x);
    }
    return {mn,mx};
}
void Clear()
{
    ll i;
    for(i=1;i<=4991;i++)
    {
        v[i].clear();
        h[i]=0;
        b[i]=0;
        a[i]=0;
        c[i]=0;
        d[i]=0;
        perm[i]=0;
    }
    for(i=1;i<=4991;i++)
        for(j=1;j<=4991;j++)
    {
        adj[i][j]=0;
    }
}
ll Bob(vector<pair<int,int>> V)
{
   Clear();
    m=V.size();
    for(i=1;i<=m;i++)
    {
        x=V[i-1].first;
        y=V[i-1].second;
        v[x].push_back(y);
        v[y].push_back(x);
        h[x]++;
        h[y]++;
    }
    n=4991;
    for(e=1;e<=31;e++)
    {
        if(e!=31)
        {
            l=(e-1)*161+1;
            r=e*161;
        }
        else
        {
            l=(e-1)*161+1;
            r=4991;
        }
        for(i=1;i<=n;i++)
        {
            if(h[i]>=2)
            {
                //printf("(%lld)\n",i);
                s=0;
                for(j=0;j<h[i];j++)
                {
                    if(l<=v[i][j]&&r>=v[i][j])
                        s++;
                }
                if(s>=2)
                {
                    b[e]=i-1;
                    //printf("%lld %lld\n",e,i-1);
                    break;
                }
            }
            if(i==n)
            {
                b[e]=-1;
            }
        }
    }
    b[0]=0;
    d[1]=1;
    d[2]=2;
    d[4]=3;
    d[8]=4;
    d[16]=5;
    for(i=0;i<=31;i++)
    {
        for(j=0;j<=31;j++)
        {
            if((i|j)==j&&d[(j-i)]!=0)
            {
                if(b[i]!=-1&&b[j]!=-1)
                {
                    a[d[j-i]]=b[i]^b[j];
                }
            }
        }
    }
    s=0;
    for(i=5;i>=1;i--)
    {
        s=s*mod+a[i];
    }
    return s;
}
};
ll Bob(vector<pair<int,int>> V)
{
   return B::Bob(V);
}

Compilation message

Alice.cpp: In function 'std::vector<std::pair<int, int> > A::Alice()':
Alice.cpp:157:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |         for(i=0;i<u.size()-1;i++)
      |                 ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 307152 KB Correct.
2 Correct 118 ms 307196 KB Correct.
3 Correct 115 ms 307296 KB Correct.
4 Correct 136 ms 307152 KB Correct.
5 Correct 128 ms 307056 KB Correct.
6 Correct 122 ms 307268 KB Correct.
7 Correct 121 ms 307208 KB Correct.
8 Correct 126 ms 307088 KB Correct.
9 Correct 120 ms 307132 KB Correct.
10 Correct 122 ms 307164 KB Correct.
11 Correct 134 ms 307252 KB Correct.
12 Correct 122 ms 307156 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 307152 KB Correct.
2 Correct 118 ms 307196 KB Correct.
3 Correct 115 ms 307296 KB Correct.
4 Correct 136 ms 307152 KB Correct.
5 Correct 128 ms 307056 KB Correct.
6 Correct 122 ms 307268 KB Correct.
7 Correct 121 ms 307208 KB Correct.
8 Correct 126 ms 307088 KB Correct.
9 Correct 120 ms 307132 KB Correct.
10 Correct 122 ms 307164 KB Correct.
11 Correct 134 ms 307252 KB Correct.
12 Correct 122 ms 307156 KB Correct.
13 Correct 124 ms 306920 KB Correct.
14 Correct 120 ms 307184 KB Correct.
15 Correct 122 ms 307100 KB Correct.
16 Correct 127 ms 307260 KB Correct.
17 Correct 137 ms 307164 KB Correct.
18 Correct 133 ms 306992 KB Correct.
19 Correct 125 ms 307024 KB Correct.
20 Correct 125 ms 307064 KB Correct.
21 Correct 129 ms 307156 KB Correct.
22 Correct 135 ms 307172 KB Correct.
23 Correct 123 ms 306904 KB Correct.
24 Correct 120 ms 307052 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 307152 KB Correct.
2 Correct 118 ms 307196 KB Correct.
3 Correct 115 ms 307296 KB Correct.
4 Correct 136 ms 307152 KB Correct.
5 Correct 128 ms 307056 KB Correct.
6 Correct 122 ms 307268 KB Correct.
7 Correct 121 ms 307208 KB Correct.
8 Correct 126 ms 307088 KB Correct.
9 Correct 120 ms 307132 KB Correct.
10 Correct 122 ms 307164 KB Correct.
11 Correct 134 ms 307252 KB Correct.
12 Correct 122 ms 307156 KB Correct.
13 Correct 124 ms 306920 KB Correct.
14 Correct 120 ms 307184 KB Correct.
15 Correct 122 ms 307100 KB Correct.
16 Correct 127 ms 307260 KB Correct.
17 Correct 137 ms 307164 KB Correct.
18 Correct 133 ms 306992 KB Correct.
19 Correct 125 ms 307024 KB Correct.
20 Correct 125 ms 307064 KB Correct.
21 Correct 129 ms 307156 KB Correct.
22 Correct 135 ms 307172 KB Correct.
23 Correct 123 ms 306904 KB Correct.
24 Correct 120 ms 307052 KB Correct.
25 Correct 134 ms 306396 KB Correct.
26 Correct 135 ms 307136 KB Correct.
27 Correct 127 ms 306900 KB Correct.
28 Correct 127 ms 306896 KB Correct.
29 Correct 124 ms 307156 KB Correct.
30 Correct 120 ms 305572 KB Correct.
31 Correct 140 ms 306660 KB Correct.
32 Correct 123 ms 337020 KB Correct.
33 Correct 139 ms 335572 KB Correct.
34 Correct 121 ms 335320 KB Correct.
35 Correct 134 ms 336612 KB Correct.
36 Correct 122 ms 335004 KB Correct.
37 Correct 122 ms 335640 KB Correct.
38 Correct 120 ms 335856 KB Correct.
39 Correct 120 ms 334548 KB Correct.
40 Correct 123 ms 336456 KB Correct.
41 Correct 120 ms 336604 KB Correct.
42 Correct 120 ms 336512 KB Correct.
43 Correct 123 ms 335204 KB Correct.
44 Correct 125 ms 335068 KB Correct.