제출 #1146734

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146734		SpyrosAliv	스핑크스 (IOI24_sphinx)	C++20	0 / 100	0 ms	416 KiB

sphinx

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

int n;
vector<vector<int>> g;

bool sim(int a, int b) { // checks if two adj nodes share color
    vector<int> qr(n, n);
    qr[a] = qr[b] = -1;
    int cnt = perform_experiment(qr);
    if (cnt == 3) return false;
    if (g[a].size() == 1 && g[b].size() == 1) {
        if (cnt == 1) return true;
        else return false;
    }
    return true;
}

vector<int> solve3() {
    int comps = 0;
    vector<int> q;
    vector<int> cols(n);
    int currCol = 0;
    for (int i = 0; i < n; i++) {
        cols[i] = currCol;
        if (i == n-1) break;
        if (sim(i, i+1)) continue;
        else currCol++;
    }
    return cols;
}

vector<int> solve12() {
    return {-1};
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    n = N;
    bool line = true;
    g.resize(n+1);
    for (int i = 0; i < n; i++) {
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
        if (min(X[i], Y[i]) != max(X[i], Y[i]) - 1) line = false;
    }
    if (n <= 50 && !line) return solve12();
    else if (line) solve3();
    return {-1};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 7
• Subtask 3: 0 / 33
• Subtask 4: 0 / 21
• Subtask 5: 0 / 36