oj.uz

답안 #99313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
99313 2019-03-02T10:27:05 Z Mercenary CEOI16_icc (CEOI16_icc) C++14
90 / 100
 163 ms 640 KB 
#include "icc.h"
#include <bits/stdc++.h>
const int maxn = 105;
using namespace std;

vector<int> P[maxn];

int papa[maxn];

int Cal(vector<int> a , vector<int> b)
{
    assert(a.size() > 0);
    int n = a.size();
    if(n == 1)return a[0];
    vector<int> tmp;
    int mid = n / 2;
    for(int i = 0 ; i < mid ; ++i)tmp.push_back(a[i]);
    if(query(tmp.size(),b.size(),tmp.data(),b.data()))return Cal(tmp,b);
    tmp.clear();
    for(int i = mid ; i < n ; ++i)tmp.push_back(a[i]);
    return Cal(tmp,b);
}

void run(int n)
{
    for(int i = 1 ; i <= n ; ++i)P[i].push_back(i) , papa[i] = i;
    for(int i = n ; i > 1 ; --i)
    {
        sort(P + 1 , P + i + 1,greater<vector<int>>());
        for(int j = 1 ; j <= i ; ++j)
            for(int c : P[j])papa[c] = j;
        vector<int> a , b;
        for(int j = 0 ; j < 8 ; ++j)
        {
            a.clear();b.clear();
            for(int k = 1 ; k <= i ; ++k)
            {
                if((k >> j) & 1)for(int c : P[k])a.push_back(c);
                else for(int c : P[k])b.push_back(c);
            }
            if(a.size() == 0 || b.size() == 0)continue;
            if(query(a.size(),b.size(),a.data(),b.data()))break;
        }
        assert(a.size() > 0 && b.size() > 0);
        int u  = Cal(a , b);
        int v = Cal(b , a);
        setRoad(u,v);
//        cout << u << " " << v << endl;
        u = papa[u];
        v = papa[v];
//        cout << u << " " << v << endl;
        if(u > v)swap(u,v);
        for(int c : P[v])papa[c] = u , P[u].push_back(c);
        if(i != v){
            for(int c : P[i])papa[c] = v;
            swap(P[v],P[i]);
        }
        P[i].clear();
    }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 512 KB Ok! 96 queries used.
2 Correct 8 ms 512 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 512 KB Ok! 531 queries used.
2 Correct 51 ms 512 KB Ok! 692 queries used.
3 Correct 52 ms 512 KB Ok! 671 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 512 KB Ok! 1435 queries used.
2 Correct 146 ms 604 KB Ok! 1680 queries used.
3 Correct 141 ms 604 KB Ok! 1613 queries used.
4 Correct 153 ms 632 KB Ok! 1559 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 640 KB Ok! 1473 queries used.
2 Correct 153 ms 568 KB Ok! 1508 queries used.
3 Correct 147 ms 628 KB Ok! 1635 queries used.
4 Correct 144 ms 632 KB Ok! 1532 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 632 KB Ok! 1650 queries used.
2 Correct 151 ms 596 KB Ok! 1626 queries used.
3 Correct 163 ms 556 KB Ok! 1655 queries used.
4 Correct 143 ms 512 KB Ok! 1610 queries used.
5 Correct 146 ms 632 KB Ok! 1492 queries used.
6 Correct 152 ms 512 KB Ok! 1578 queries used.

Subtask #6
0 / 10.0

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