oj.uz

Submission #231086

# Submission time Handle Problem Language Result Execution time Memory
231086 2020-05-12T16:23:14 Z nicolaalexandra ICC (CEOI16_icc) C++14
90 / 100
 197 ms 640 KB 
/// sincer nu inteleg dc sunt asa proasta
#include <bits/stdc++.h>
#include "icc.h"
#define DIM 200
using namespace std;

int n;
int v[DIM],t[DIM],aux[DIM],a[DIM],b[DIM];

/*int query (int n, int m, int a[], int b[]){
    int ans;
    cout<<n<<" ";
    for (int i=0;i<n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    cout<<m<<" ";
    for (int i=0;i<m;i++)
        cout<<b[i]<<" ";
    cout<<endl;
    cin>>ans;
    return ans;
}
void setRoad (int x, int y){
    cout<<x<<" "<<y<<endl;
}*/

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
void _union (int x, int y){
    int radx = get_rad (x), rady = get_rad (y);

    if (t[radx] < t[rady]){
        t[radx] += t[rady];
        t[rady] = radx;
    } else {
        t[rady] += t[radx];
        t[radx] = rady;
    }

}

void run (int n){
    int k,k2,el,i,x,y;
    for (i=1;i<=n;i++)
        t[i] = -1;
    for (int pas=1;pas<n;pas++){
        /// impart componentele conexe in doua multimi

        for (int bit=0;bit<7;bit++){
            k = 0, k2 = 0;

            for (i=1;i<=n;i++){
                int val = get_rad(i);
                if (val&(1<<bit))
                    a[k++] = i;
                else b[k2++] = i;
            }

            if (!k || !k2)
                continue;

            if (bit == 6 || query(k,k2,a,b)){ /// am gasit cele doua multimi

                while (k > 1){
                    int mid = k/2;

                    if (query(mid,k2,a,b))
                        k = mid;
                    else {
                        for (int i=mid;i<k;i++)
                            a[i-mid] = a[i];
                        k -= mid;
                    }
                }
                x = a[0];


                while (k2 > 1){
                    int mid = k2/2;

                    if (query(k,mid,a,b))
                        k2 = mid;
                    else {
                        for (int i=mid;i<k2;i++)
                            b[i-mid] = b[i];
                        k2 -= mid;
                    }
                }
                y = b[0];

                setRoad(x,y);

                _union (x,y);

                break;
            }
        }
    }
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:46:14: warning: unused variable 'el' [-Wunused-variable]
     int k,k2,el,i,x,y;
              ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Ok! 101 queries used.
2 Correct 12 ms 512 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 512 KB Ok! 544 queries used.
2 Correct 56 ms 512 KB Ok! 692 queries used.
3 Correct 58 ms 512 KB Ok! 678 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 512 KB Ok! 1366 queries used.
2 Correct 162 ms 632 KB Ok! 1629 queries used.
3 Correct 129 ms 512 KB Ok! 1362 queries used.
4 Correct 153 ms 512 KB Ok! 1502 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 636 KB Ok! 1412 queries used.
2 Correct 145 ms 640 KB Ok! 1470 queries used.
3 Correct 163 ms 632 KB Ok! 1636 queries used.
4 Correct 131 ms 512 KB Ok! 1350 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 512 KB Ok! 1595 queries used.
2 Correct 156 ms 512 KB Ok! 1626 queries used.
3 Correct 157 ms 512 KB Ok! 1624 queries used.
4 Correct 157 ms 384 KB Ok! 1559 queries used.
5 Correct 142 ms 592 KB Ok! 1437 queries used.
6 Correct 153 ms 512 KB Ok! 1577 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 512 KB Ok! 1625 queries used.
2 Incorrect 197 ms 512 KB Too many queries! 1649 out of 1625