oj.uz

Submission #585557

# Submission time Handle Problem Language Result Execution time Memory
585557 2022-06-29T05:06:15 Z 조영욱(#8387) ICC (CEOI16_icc) C++14
0 / 100
 2 ms 756 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

int n;

bool tree[101];
        vector<int> in;
        vector<int> out;

typedef pair<int,int> P;

int temp1[101];
int temp2[101];

bool que(vector<int> one,vector<int> two) {
    for(int i=0;i<one.size();i++) {
        temp1[i]=one[i];
    }
    for(int i=0;i<two.size();i++) {
        temp2[i]=two[i];
    }
    if (one.empty()||two.empty()) {
        return false;
    }
    return query(one.size(),two.size(),temp1,temp2);
}

P f1() {
    int xo=0; //a^b
    for(int bit=0;bit<7;bit++) {
        vector<int> one;
        vector<int> two;
        for(int i=1;i<=n;i++) {
            if (!tree[i]) {
                if (bit&(1<<i)) {
                    one.push_back(i);
                }
                else {
                    two.push_back(i);
                }
            }
        }
        if (que(one,two)) {
            xo+=(1<<bit);
        }
    }
    vector<int> one;
    vector<int> two;
    for(int i=1;i<=n;i++) {
        if (tree[i]) {
            continue;
        }
        int nt=(i^xo);
        if (nt<=n&&!tree[nt]&&i<nt) {
            one.push_back(i);
        }
        if (nt<=n&&!tree[nt]&&i>nt) {
            two.push_back(i);
        }
    }
    int l=0;
    int r=two.size()-1;
    while (l<r) {
        int mid=(l+r)/2;
        vector<int> temp;
        for(int i=l;i<=mid;i++) {
            temp.push_back(two[i]);
        }
        if (que(one,temp)) {
            r=mid;
        }
        else {
            l=mid+1;
        }
    }
    return P(two[l],two[l]^xo);
}

P f2() {
    int l=0;
    int r=in.size()-1;
    while (l<r) {
        int mid=(l+r)/2;
        vector<int> temp;
        for(int i=l;i<=mid;i++) {
            temp.push_back(in[i]);
        }
        if (que(temp,out)) {
            r=mid;
        }
        else {
            l=mid+1;
        }
    }
    int one=in[l];
    l=0;
    r=out.size()-1;
    while (l<r) {
        int mid=(l+r)/2;
        vector<int> temp;
        for(int i=l;i<=mid;i++) {
            temp.push_back(out[i]);
        }
        if (que(in,temp)) {
            r=mid;
        }
        else {
            l=mid+1;
        }
    }
    int two=out[l];
    return P(one,two);
}

void run(int nn) {
    n=nn;
    for(int i=0;i<n-1;i++) {
        in.clear();
        out.clear();
        for(int j=1;j<=n;j++) {
            if (tree[j]) {
                in.push_back(j);
            }
            else {
                out.push_back(j);
            }
        }
        P got;
        if (que(in,out)) {
            got=f2();
        }
        else {
            got=f1();
        }
        setRoad(got.first,got.second);
        tree[got.first]=true;
        tree[got.second]=true;
    }
}

Compilation message

icc.cpp: In function 'bool que(std::vector<int>, std::vector<int>)':
icc.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<one.size();i++) {
      |                 ~^~~~~~~~~~~
icc.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<two.size();i++) {
      |                 ~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 752 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -