| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1362957 | afric | Toy Design (EGOI22_toydesign) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "toydesign.h"
using namespace std;
// DEBUG
/*int Connected(int a, int i, int j) {
cout << "? " << a << ' ' << i << ' ' << j << endl;
int ans;
cin >> ans;
return ans;
}*/
void binarySearch(int i, vector<int> &allTo, vector<int> &component) {
int l = 0;
int r = (i-1);
while (l < r) {
int mid = (l+r) / 2;
if (Connected(allTo[mid],i+1,mid+1)==allTo[mid]) {
// i is connected to some component prior to mid -> no new design created
r = mid;
}
else {
// is not connected to any component prior to mid -> new design created
l = (mid+1);
}
}
component[i] = component[l];
}
// DEBUG
/*void DescribeDesign(vector<pair<int,int>> res) {
for (pair<int,int> edge : res) {
cout << edge.first << ' ' << edge.second << endl;
}
}*/
void construct(vector<int> &component) {
unordered_map<int,vector<int>> c;
for (int i = 0; i < component.size(); i++) {
if (c.find(component[i])==c.end()) {
c[component[i]] = {i};
}
else {
c[component[i]].push_back(i);
}
}
vector<pair<int,int>> res;
for (auto p : c) {
if (p.second.size() > 1) {
for (int i = 1; i < p.second.size(); i++) {
res.push_back({p.second[0] + 1,p.second[i] + 1});
}
}
}
DescribeDesign(res);
}
void ToyDesign(int n, int max_ops) {
int designs = 0;
vector<int> allTo(n, 0);
vector<int> component; component.reserve(n);
for (int i = 0; i < n; i++) {
component.push_back(i);
}
for (int i = 1; i < n; i++) {
int design = Connected(allTo[i-1], i, i+1);
allTo[i] = design;
if (design == allTo[i-1]) {
binarySearch(i,allTo,component);
}
}
construct(component);
}
// DEBUG
/*int main() {
ToyDesign(4,20);
return 0;
}*/