oj.uz

Submission #1084551

# Submission time Handle Problem Language Result Execution time Memory
1084551 2024-09-06T11:30:10 Z MMihalev ICC (CEOI16_icc) C++14
100 / 100
 105 ms 856 KB 
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#include<unordered_map>
#include "icc.h"
using namespace std;
const int MAX_N=1e3+3;
int a[MAX_N];
int b[MAX_N];
int sza,szb;
vector<int>v1,v2;
vector<vector<int>>comps;
vector<int>comp;
vector<int>g[MAX_N];
int used[MAX_N];

void dfs(int u)
{
    used[u]=1;
    comp.push_back(u);
    for(int v:g[u])
    {
        if(used[v])continue;
        dfs(v);
    }
}
void toarray(int l,int r,vector<int>& v,bool f)
{
    if(f==0)
    {
        sza=0;
        for(int i=l;i<=r;i++)
        {
            a[sza++]=v[i];
        }
    }
    else
    {
        szb=0;
        for(int i=l;i<=r;i++)
        {
            b[szb++]=v[i];
        }
    }
}
pair<int,int>guessedge()
{
    int l=0,r=v1.size()-1,u,v;
    while(l!=r)
    {
        int mid=(l+r)/2;
        toarray(l,mid,v1,0);
        toarray(0,v2.size()-1,v2,1);
        if(query(sza,szb,a,b))
        {
            r=mid;
        }
        else l=mid+1;
    }
    u=v1[l];
    int posu=l;

    l=0;
    r=v2.size()-1;
    while(l!=r)
    {
        int mid=(l+r)/2;
        toarray(posu,posu,v1,0);
        toarray(l,mid,v2,1);
        if(query(sza,szb,a,b))
        {
            r=mid;
        }
        else l=mid+1;
    }
    v=v2[l];
    return {u,v};
}
vector<vector<int>>c1,c2;
void toarray2()
{
    sza=0;
    for(auto c:c1)
    {
        for(auto d:c)
        {
            a[sza++]=d;
        }
    }
    szb=0;
    for(auto c:c2)
    {
        for(auto d:c)
        {
            b[szb++]=d;
        }
    }
}
bool in(int bit,int mask)
{
    return (((1<<bit)&(mask))!=0);
}
void separate()
{
    int id1=0,id2=0,xo=0,bit=0;
    int sz=comps.size()-1;
    for(int bi=0;(1<<bi)<=sz;bi++)
    {
        c1.clear();c2.clear();
        for(int i=0;i<=sz;i++)
        {
            if(in(bi,i))
            {
                c1.push_back(comps[i]);
            }
            else c2.push_back(comps[i]);
        }

        toarray2();
        if(query(sza,szb,a,b)){xo+=(1<<bi);bit=bi;}
    }
    id2+=(1<<bit);

    for(int bi=0;(1<<bi)<=sz;bi++)
    {
        if(bi==bit)continue;

        if(in(bi,xo))
        {
            c1.clear();c2.clear();
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==0)c1.push_back(comps[i]);
            }
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==1 && in(bit,i)==1)c2.push_back(comps[i]);
            }

            toarray2();
            if(query(sza,szb,a,b))
            {
                id2+=(1<<bi);
            }
            else id1+=(1<<bi);
        }
        else
        {
            c1.clear();c2.clear();
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==0)c1.push_back(comps[i]);
            }
            for(int i=0;i<=sz;i++)
            {
                if(in(bi,i)==0 && in(bit,i)==1)c2.push_back(comps[i]);
            }

            toarray2();
            if(!query(sza,szb,a,b))
            {
                id2+=(1<<bi);
                id1+=(1<<bi);
            }
        }
    }

    v1=comps[id1];
    v2=comps[id2];
}
void run(int N)
{
    for(int steps=1;steps<=N-1;steps++)
    {
        comps.clear();
        for(int i=1;i<=N;i++)
        {
            used[i]=0;
        }
        for(int i=1;i<=N;i++)
        {
            if(used[i]==0)
            {
                comp.clear();
                dfs(i);
                comps.push_back(comp);
            }
        }

        separate();

        int u,v;
        tie(u,v)=guessedge();
        setRoad(u,v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Ok! 117 queries used.
2 Correct 4 ms 604 KB Ok! 116 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 600 KB Ok! 641 queries used.
2 Correct 22 ms 604 KB Ok! 576 queries used.
3 Correct 24 ms 680 KB Ok! 630 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 672 KB Ok! 1596 queries used.
2 Correct 65 ms 664 KB Ok! 1356 queries used.
3 Correct 75 ms 600 KB Ok! 1609 queries used.
4 Correct 74 ms 604 KB Ok! 1580 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 604 KB Ok! 1568 queries used.
2 Correct 74 ms 600 KB Ok! 1572 queries used.
3 Correct 105 ms 600 KB Ok! 1587 queries used.
4 Correct 87 ms 604 KB Ok! 1594 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 600 KB Ok! 1530 queries used.
2 Correct 72 ms 856 KB Ok! 1556 queries used.
3 Correct 71 ms 604 KB Ok! 1522 queries used.
4 Correct 73 ms 600 KB Ok! 1587 queries used.
5 Correct 94 ms 600 KB Ok! 1596 queries used.
6 Correct 73 ms 600 KB Ok! 1600 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 604 KB Ok! 1587 queries used.
2 Correct 72 ms 604 KB Ok! 1556 queries used.