oj.uz

Submission #974105

# Submission time Handle Problem Language Result Execution time Memory
974105 2024-05-02T19:38:24 Z HoriaHaivas ICC (CEOI16_icc) C++14
90 / 100
 88 ms 860 KB 
/*
    "care a facut teste cu Lattice reduction attack e ciudat"
    "linistiti va putin"
    - 2023 -
*/
#include<bits/stdc++.h>
#include "icc.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

int n;
int root[105];
int sz[105];
int comp[105][105];
bool connected[105][105];
int aquery[105];
int aqsz;
int bquery[105];
int bqsz;
int c[105];
int d[105];
bool seen[105];

void unite(int a, int b)
{
    a=root[a];
    b=root[b];
    if (a==b)
        return;
    if(sz[a]<sz[b])
    {
        swap(a,b);
    }
    int i;
    for (i=0; i<sz[b]; i++)
    {
        comp[a][sz[a]]=comp[b][i];
        sz[a]++;
        root[comp[b][i]]=a;
    }
}

/*
int query(int sza, int szb, int a[], int b[])
{
    int i,j;
    for (i=0; i<sza; i++)
    {
        for (j=0; j<szb; j++)
        {
            if (connected[a[i]][b[j]])
            {
                return 1;
            }
        }
    }
    return 0;
}
*/

void add(int type, int &sza, int b[], int szb)
{
    int i;
    if (type==1)
    {
        for (i=0; i<szb; i++)
        {
            c[sza]=b[i];
            sza++;
        }
    }
    else if (type==2)
    {
        for (i=0; i<szb; i++)
        {
            aquery[sza]=b[i];
            sza++;
        }
    }
    else if (type==3)
    {
        for (i=0; i<szb; i++)
        {
            bquery[sza]=b[i];
            sza++;
        }
    }
}

void addlr(int type, int &sza, int b[], int lb, int rb)
{
    int i;
    if (type==1)
    {
        for (i=lb; i<=rb; i++)
        {
            c[sza]=b[i];
            sza++;
        }
    }
    else if (type==2)
    {
        for (i=lb; i<=rb; i++)
        {
            aquery[sza]=b[i];
            sza++;
        }
    }
    else if (type==3)
    {
        for (i=lb; i<=rb; i++)
        {
            bquery[sza]=b[i];
            sza++;
        }
    }
}

bool compara(int j)
{
    int i;
    for (i=1; i<=n; i++)
    {
        seen[i]=0;
    }
    int x;
    for (i=1; i<=n; i++)
    {
        x=root[i];
        if (!seen[x])
        {
            if (x&(1<<j))
                add(2,aqsz,comp[x],sz[x]);
            else
                add(3,bqsz,comp[x],sz[x]);
            seen[x]=1;
        }
    }
    /*
    debugs(j);
    debugs(aqsz);
    debug(bqsz);
    for (i=0;i<aqsz;i++)
    {
         debug(aquery[i]);
    }
    for (i=0;i<bqsz;i++)
    {
         debug(bquery[i]);
    }
    */
    return query(aqsz,bqsz,aquery,bquery);
}

pair<int,int> find_road()
{
    int i,j;
    for (i=0; i<7 && (1<<i)<=n; i++)
    {
        aqsz=0;
        bqsz=0;
        //debugs(i);
        //debug(compara(i));
        if (compara(i)==1)
        {
            break;
        }
    }
    int l,r,mid,apoz,bpoz,csize;
    l=0;
    r=aqsz-1;
    while (l<r)
    {
        mid=l+(r-l)/2;
        csize=0;
        addlr(1,csize,aquery,l,mid);
        if (query(csize,bqsz,c,bquery)==1)
        {
            r=mid;
        }
        else
        {
            if (l!=mid)
            l=mid+1;
            else
            l=r;
        }
    }
    apoz=aquery[r];
    d[0]=apoz;
    l=0;
    r=bqsz-1;
    while (l<r)
    {
        mid=l+(r-l)/2;
        csize=0;
        addlr(1,csize,bquery,l,mid);
        if (query(csize,1,c,d)==1)
        {
            r=mid;
        }
        else
        {
            if (l!=mid)
            l=mid+1;
            else
            l=r;
        }
    }
    bpoz=bquery[r];
    return {apoz,bpoz};
}


/*
void build_road()
{
    int a,b;
    cin >> a >> b;
    connected[a][b]=1;
    connected[b][a]=1;
}

void setroad(int a, int b)
{
    cout << "am gasit lol : ";
    cout << a << " " << b << "\n";
    //unite(a,b);
}
*/

void run(int _n)
{
    n=_n;
    int pasi,i;
    pair<int,int> ans;
    for (i=1; i<=n; i++)
    {
        root[i]=i;
        comp[i][0]=i;
        sz[i]=1;
    }
    pasi=0;
    while (pasi<n-1)
    {
        //build_road();///asta trebuie comentat
        ans=find_road();
        setRoad(ans.first,ans.second);
        unite(ans.first,ans.second);
        pasi++;
    }
}

/*
signed main()
{
    //ifstream fin("secvp.in");
    //ofstream fout("secvp.out");
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
    int en;
    cin >> en;
    run(en);
}
*/

Compilation message

icc.cpp: In function 'std::pair<int, int> find_road()':
icc.cpp:160:11: warning: unused variable 'j' [-Wunused-variable]
  160 |     int i,j;
      |           ^

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 600 KB Ok! 533 queries used.
2 Correct 32 ms 600 KB Ok! 666 queries used.
3 Correct 26 ms 604 KB Ok! 654 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 604 KB Ok! 1316 queries used.
2 Correct 79 ms 664 KB Ok! 1637 queries used.
3 Correct 64 ms 604 KB Ok! 1312 queries used.
4 Correct 74 ms 604 KB Ok! 1505 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 600 KB Ok! 1474 queries used.
2 Correct 77 ms 604 KB Ok! 1502 queries used.
3 Correct 84 ms 604 KB Ok! 1657 queries used.
4 Correct 75 ms 656 KB Ok! 1309 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 860 KB Ok! 1634 queries used.
2 Correct 78 ms 600 KB Ok! 1615 queries used.
3 Correct 83 ms 604 KB Ok! 1648 queries used.
4 Correct 78 ms 676 KB Ok! 1579 queries used.
5 Correct 72 ms 604 KB Ok! 1463 queries used.
6 Correct 80 ms 604 KB Ok! 1565 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 87 ms 656 KB Too many queries! 1653 out of 1625
2 Halted 0 ms 0 KB -