oj.uz

답안 #128829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128829 2019-07-11T09:59:42 Z zubec CEOI16_icc (CEOI16_icc) C++14
61 / 100
 227 ms 736 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

int n;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int sz1, sz2, A[110], B[110];

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);
}

int dsu[110];

int dsu_get(int v){
    if (v == dsu[v])
        return v;
    return dsu[v] = dsu_get(dsu[v]);
}

void dsu_unite(int a, int b){
    a = dsu_get(a);
    b = dsu_get(b);
    dsu[b] = a;
}

vector <int> g[110];

void run(int N){
    n = N;
    for (int i = 1; i <= n; i++){
        dsu[i] = i;
    }
    for (int tt = 1; tt < n; tt++){
        vector <int> vec;
        for (int i = 1; i <= n; i++)
            g[i].clear();
        for (int i = 1; i <= n; i++){
            vec.push_back(dsu_get(i));
            g[dsu_get(i)].push_back(i);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        while(1){
            shuffle(vec.begin(), vec.end(), rnd);
            int pos = vec.size()/2-1;

            vector <int> vec1, vec2;
            for (int j = 0; j <= pos; j++){
                for (int l = 0; l < g[vec[j]].size(); l++)
                    vec1.push_back(g[vec[j]][l]);
            }
            for (int j = pos+1; j < vec.size(); j++){
                for (int l = 0; l < g[vec[j]].size(); l++)
                    vec2.push_back(g[vec[j]][l]);
            }
            if (!my_query(vec1, vec2))
                continue;
            int l = 0, r = vec1.size()-1;
            while(l < r){
                int mid = (l+r)>>1;
                vector <int> cur;
                for (int j = l; j <= mid; j++)
                    cur.push_back(vec1[j]);
                if (my_query(cur, vec2))
                    r = mid; else
                    l = mid+1;
            }
            int a = vec1[l];
            l = 0, r = vec2.size();
            while(l < r){
                int mid = (l+r)>>1;
                vector <int> cur;
                for (int j = l; j <= mid; j++)
                    cur.push_back(vec2[j]);
                if (my_query(vec1, cur))
                    r = mid; else
                    l = mid+1;
            }
            int b = vec2[l];
            setRoad(a, b);
            dsu_unite(a, b);
            break;
        }
    }
}

/**

4
2 4
1 3
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:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec2.size(); i++)
                     ~~^~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:57:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int l = 0; l < g[vec[j]].size(); l++)
                                 ~~^~~~~~~~~~~~~~~~~~
icc.cpp:60:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = pos+1; j < vec.size(); j++){
                                 ~~^~~~~~~~~~~~
icc.cpp:61:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int l = 0; l < g[vec[j]].size(); l++)
                                 ~~^~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 504 KB Ok! 107 queries used.
2 Correct 10 ms 504 KB Ok! 114 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 504 KB Ok! 540 queries used.
2 Correct 65 ms 504 KB Ok! 834 queries used.
3 Correct 64 ms 504 KB Ok! 825 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 648 KB Ok! 1546 queries used.
2 Correct 227 ms 568 KB Ok! 2127 queries used.
3 Correct 177 ms 604 KB Ok! 1730 queries used.
4 Correct 172 ms 736 KB Ok! 1684 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 576 KB Ok! 1657 queries used.
2 Correct 170 ms 612 KB Ok! 1651 queries used.
3 Correct 198 ms 632 KB Ok! 1881 queries used.
4 Correct 163 ms 504 KB Ok! 1607 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 199 ms 504 KB Too many queries! 1886 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 200 ms 608 KB Too many queries! 1901 out of 1625
2 Halted 0 ms 0 KB -