Submission #869513

#	Time	Username	Problem	Language	Result	Execution time	Memory
869513		Andrey	ICC (CEOI16_icc)	C++14	100 / 100	92 ms	936 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> dsu(10001);
vector<int> haha[1001];

int bin(int a, int b) {
    int l = 0,r = haha[a].size()-1;
    int yay[haha[b].size()];
    for(int i = 0; i < haha[b].size(); i++) {
        yay[i] = haha[b][i];
    }
    while(l < r) {
        int m = (l+r)/2;
        int wut[m-l+1];
        for(int i = l; i <= m; i++) {
            wut[i-l] = haha[a][i];
        }
        if(query(haha[b].size(),m-l+1,yay,wut)) {
            r = m;
        }
        else {
            l = m+1;
        }
    }
    return haha[a][l];
}

int wow(vector<int> a, vector<int> b) {
    vector<int> wut(0);
    vector<int> yay(0);
    for(int i = 0; i < a.size(); i++) {
        for(int j = 0; j < haha[a[i]].size(); j++) {
            wut.push_back(haha[a[i]][j]);
        }
    }
    for(int i = 0; i < b.size(); i++) {
        for(int j = 0; j < haha[b[i]].size(); j++) {
            yay.push_back(haha[b[i]][j]);
        }
    }
    int c[wut.size()],d[yay.size()];
    for(int i = 0; i < wut.size(); i++) {
        c[i] = wut[i];
    }
    for(int i = 0; i < yay.size(); i++) {
        d[i] = yay[i];
    }
    return query(wut.size(),yay.size(),c,d);
}

pair<int,int> dude(int br) {
    vector<int> a(0);
    vector<int> b(0);
    bool yay[20];
    int p = -1,x = 0,y = 0;
    for(int i = 0; (1 << i) <= br; i++) {
        a.clear();
        b.clear();
        for(int j = 0; j < br; j++) {
            if((1 << i)&j) {
                a.push_back(j);
            }
            else {
                b.push_back(j);
            }
        }
        yay[i] = wow(a,b);
        if(p == -1 && yay[i]) {
            p = i;
        }
    }
    for(int i = 0; (1 << i) <= br; i++) {
        if(i != p) {
            a.clear();
            b.clear();
            for(int j = 0; j < br; j++) {
                if(((1 << i)&j) && ((1 << p)&j)) {
                    a.push_back(j);
                }
                else {
                    b.push_back(j);
                }
            }
            bool yeah = wow(a,b);
            if(yeah) {
                x+=(1 << i);
            }
            if(yeah != yay[i]) {
                y+=(1 << i);
            }
        }
        else {
            x+=(1 << p);
        }
    }
    return {x,y};
}

int calc(int a) {
    int c = a;
    while(dsu[c] != c) {
        c = dsu[c];
    }
    return c;
}

void edge(int a, int b) {
    a = calc(a),b = calc(b);
    dsu[a] = b;
}

void run(int N) {
    n = N;
    for(int i = 1; i <= n; i++) {
        dsu[i] = i;
    }
    for(int i = 0; i < n-1; i++) {
        int a = -1,b = -1,br = 0;
        vector<bool> yay(n+1,true);
        for(int j = 0; j < n; j++) {
            haha[j].clear();
            for(int y = 1; y <= n; y++) {
                if(yay[y]) {
                    if(haha[j].empty() || calc(haha[j][0]) == calc(y)) {
                        haha[j].push_back(y);
                        yay[y] = false;
                    }
                }
            }
            if(haha[j].empty()) {
                break;
            }
            br++;
        }
        pair<int,int> q = dude(br);
        a = bin(q.first,q.second);
        b = bin(q.second,q.first);
        edge(a,b);
        setRoad(a,b);
    }
}

Compilation message (stderr)

icc.cpp: In function 'int bin(int, int)':
icc.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i < haha[b].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
icc.cpp: In function 'int wow(std::vector<int>, std::vector<int>)':
icc.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < a.size(); i++) {
      |                    ~~^~~~~~~~~~
icc.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0; j < haha[a[i]].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
icc.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < b.size(); i++) {
      |                    ~~^~~~~~~~~~
icc.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 0; j < haha[b[i]].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
icc.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < wut.size(); i++) {
      |                    ~~^~~~~~~~~~~~
icc.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < yay.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10