oj.uz

Submission #95015

# Submission time Handle Problem Language Result Execution time Memory
95015 2019-01-26T19:06:07 Z zubec ICC (CEOI16_icc) C++14
0 / 100
 384 ms 632 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int dsu[N];

int sz1, sz2, a[N], b[N];

int my_query(vector <int> &vec1, vector <int> &vec2){
    sz1 = sz2 = 0;
    for (int i = 0; i < vec1.size(); i++){
        a[sz1++] = vec1[i];
    }
    for (int i = 0; i < vec2.size(); i++){
        b[sz2++] = vec2[i];
    }
    return query(sz1, sz2, a, b);
}

void print(vector <int> &vec){
    for (int x : vec)
        cout << x << ' ';
    cout << endl;
}

void run(int n){
    set<int> q;
    for (int i = 1; i <= n; i++){
        dsu[i] = i;
        q.insert(i);
    }
    while(q.size() > 1){
        for (auto it1 = q.begin(); it1 != q.end(); it1++){
            int v = *it1;

            vector <int> vec1, vec2;
            vec1.push_back(v);
            for (auto it = q.begin(); it != q.end(); it++){
                if (*it != v)
                    vec2.push_back(*it);
            }

            if (my_query(vec1, vec2) == 0){
                continue;
            }
            int l = 0, r = vec2.size()-1;
            while(l < r){
                int mid = (l+r)>>1;
                vector <int> vec3;
                for (int j = 0; j <= mid; j++)
                    vec3.push_back(vec2[j]);
                if (my_query(vec1, vec3))
                    r = mid; else
                    l = mid+1;
            }
            int u = vec2[l];
            //cout << v << ' ' << u << endl;
            q.erase(u);
            setRoad(v, u);
            break;
        }

    }

}

/**

5
2 3
2 1
1 5
1 4


*/

Compilation message

icc.cpp: In function 'int my_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:13:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec1.size(); i++){
                     ~~^~~~~~~~~~~~~
icc.cpp:16:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec2.size(); i++){
                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 504 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 308 ms 560 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 560 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 332 ms 632 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 604 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 568 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -