제출 #1191388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191388		onbert	Simurgh (IOI17_simurgh)	C++17	19 / 100	435 ms	3888 KiB

simurgh

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

const int maxn = 505;
int n;
int id[maxn][maxn];
bool a[maxn][maxn], gold[maxn][maxn];

int qry() {
    vector<int> ask;
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (a[i][j]) ask.push_back(id[i][j]);
    // for (int i:ask) cout << i << " "; cout << endl;
    return count_common_roads(ask);
}


int cnt(int l, int r, int pos) {
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) a[i][j] = 0;
    int cur = 0;
    for (int i=0;i<n;i++) {
        if (l <= i && i <= r) a[i][pos] = 1;
        else {
            a[i][n-1] = 1;
            cur -= gold[i][n-1];
        }
    }
    cur += qry();
    return cur;
}


vector<int> find_roads(int N, vector<int> U, vector<int> V) {
    n = N;
	for (int i=0;i<n;i++) for (int j=0;j<n;j++) id[i][j] = -1, a[i][j] = 0, gold[i][j] = 0;
    for (int i=0;i<U.size();i++) {
        if (U[i] > V[i]) swap(U[i], V[i]);
        id[U[i]][V[i]] = i;
    }

    for (int i=0;i<n-2;i++) a[i][i+1] = 1;
    vector<int> vec;
    for (int i=0;i<n-1;i++) {
        a[i][n-1] = 1;
        vec.push_back(qry());
        a[i][n-1] = 0;
    }
    int mx = *max_element(vec.begin(), vec.end());
    for (int i=0;i<n-1;i++) if (vec[i] == mx) gold[i][n-1] = 1;
    // cout << "test\n";

    for (int i=1;i<n-1;i++) {
        int all = cnt(0, i-1, i);
        // cout << i << " " << all << endl;
        for (int j=1;j<=all;j++) {
            int l = 0, r = i-1;
            while (l < r) {
                int mid = (l+r+1)/2;
                if (cnt(mid, i-1, i) >= j) l = mid;
                else r = mid-1;
            }
            gold[l][i] = 1;
        }
    }
    vector<int> ans;
    for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) if (gold[i][j]) {
        ans.push_back(id[i][j]);
        // cout << i << " " << j << endl;
    }
    return ans;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30