oj.uz

답안 #532316

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
532316 2022-03-02T17:27:33 Z gg123_pe CEOI16_icc (CEOI16_icc) C++14
90 / 100
 141 ms 500 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std; 

typedef pair<int,int> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define ff first 
#define ss second 

int n, p[105], a[105], b[105]; 
vector <int> adj[105], parents; 

void divide(vector <ii> v1, vector <ii> v2, vector <ii> &a1, vector <ii> &a2){
    for(auto p: v1){
        int l = p.ff, r = p.ss, sz = r-l+1; 
        if(sz > 1) a1.push_back({l, l+(sz/2)-1}), a2.push_back({l+(sz/2), r}); 
        else a1.push_back({l, r}); 
    }
    for(auto p: v2){
        int l = p.ff, r = p.ss, sz = r-l+1; 
        if(sz > 1) a1.push_back({l, l+(sz/2)-1}), a2.push_back({l+(sz/2), r}); 
        else a1.push_back({l, r}); 
    }
}

vector <int> get(vector <ii> v){
    vector <int> ra; 
    for(auto p: v){
        int l = p.ff, r = p.ss; 
        f(i,l,r+1) for(int x: adj[parents[i]]) ra.push_back(x);
    }
    return ra; 
}
bool Q(int x, int y, vector <int> ra, vector <int> ta){
    f(i,0,x) a[i] = ra[i]; 
    f(i,0,y) b[i] = ta[i]; 
    return query(x, y, a, b); 
}
void run(int x){ 
    n = x; 
    f(i,1,n+1) adj[i] = {i}, p[i] = i; 

    f(ra,1,n){
        parents.clear(); vector <ii> v1, v2, aux;  vector <int> V1, V2; 
        f(i,1,n+1) 
            if(adj[i].size()) {
                int k; 
                f(s,0,10) if(i&(1<<s)) {k = s; break;} 
                aux.push_back({k, i}); 
            }
        sort(aux.begin(), aux.end());
        int sz = aux.size(); 
        f(i,0,sz) parents.push_back(aux[i].ss); 

        v1 = {{0, sz-1}}; 
        while(1){
            vector <ii> aux1, aux2; 
            divide(v1, v2, aux1, aux2);
            v1 = aux1, v2 = aux2; 
            V1 = get(v1), V2 = get(v2); 
            if(Q(V1.size(), V2.size(), V1, V2)) break;
        }
        while(V1.size() > 1){
            int s = V1.size();
            vector <int> ra, ta; 
            f(i,0,s/2) ra.push_back(V1[i]); f(i,s/2,s) ta.push_back(V1[i]);

            if(Q(V2.size(), ra.size(), V2, ra)) V1 = ra; 
            else V1 = ta; 
        }
        while(V2.size() > 1){
            int s = V2.size();
            vector <int> ra, ta; 
            f(i,0,s/2) ra.push_back(V2[i]); f(i,s/2,s) ta.push_back(V2[i]);

            if(Q(V1.size(), ra.size(), V1, ra)) V2 = ra; 
            else V2 = ta; 
        }
        int x = V1[0], y = V2[0];
        setRoad(x, y);
        x = p[x], y = p[y]; 
        for(int wi: adj[x]) p[wi] = y, adj[y].push_back(wi);
        adj[x].clear();  
    }
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 460 KB Ok! 108 queries used.
2 Correct 6 ms 460 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 460 KB Ok! 546 queries used.
2 Correct 33 ms 460 KB Ok! 708 queries used.
3 Correct 33 ms 460 KB Ok! 700 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 111 ms 500 KB Ok! 1547 queries used.
2 Correct 119 ms 500 KB Ok! 1704 queries used.
3 Correct 113 ms 480 KB Ok! 1671 queries used.
4 Correct 103 ms 500 KB Ok! 1587 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 480 KB Ok! 1641 queries used.
2 Correct 97 ms 492 KB Ok! 1512 queries used.
3 Correct 133 ms 480 KB Ok! 1704 queries used.
4 Correct 107 ms 500 KB Ok! 1570 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 488 KB Ok! 1703 queries used.
2 Correct 115 ms 496 KB Ok! 1703 queries used.
3 Correct 134 ms 480 KB Ok! 1700 queries used.
4 Correct 112 ms 460 KB Ok! 1690 queries used.
5 Correct 98 ms 460 KB Ok! 1560 queries used.
6 Correct 105 ms 484 KB Ok! 1554 queries used.

Subtask #6
0 / 10.0

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