| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1106593 | salmon | Fun Tour (APIO20_fun) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> createFunTour(int N, int Q){
int lst[N + 1];
int d[N + 1];
int d1[N + 2][2];
set<pair<int,int>,greater<pair<int,int>>> sat[3];
for(int i = 0; i < N; i++){
lst[i] = attractionsBehind(0,i);
}
pair<int,int> ii = {N + 90,-1};
for(int i = 0; i < N; i++){
if(lst[i] >= (N+1)/2 ) ii = min(ii,{lst[i],i});
}
int it = ii.second;
for(int i = 0; i < N; i++){
d[i] = hoursRequired(it,i);
}
vector<int> tee;
for(int i = 0; i < N; i++){
if(d[i] == 1) tee.push_back(i);
}
if(tee.size() == 1){
return {0,1};
}
else{
for(int i = 0; i < N; i++){
d1[i][0] = hoursRequired(i,tee[0]);
d1[i][1] = hoursRequired(i,tee[1]);
}
for(int i = 0; i < N; i++){
if(i == it) continue;
if(d1[i][0] < d[i]){
sat[0].insert({d[i],i});
}
else if(d1[i][1] < d[i]){
sat[1].insert({d[i],i});
}
else sat[2].insert({d[i],i});
}
int prev = -1;
vector<int> ans = {};
N = 2;
sat[0] = {1};
sat[1] = {2};
sat[2];
while(max(max(sat[0].size(),sat[1].size() ), sat[2].size()) < (N/2) ){
assert (!(sat[0].empty()) && !(sat[1].empty()) && !(sat[2].empty()));
if(prev == -1){
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].begin() -> first,i});
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
else{
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) if(i != prev) ii = max(ii, {sat[i].begin() -> first,i});
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
}
pair<int,int> ii = {-10,-1};
for(int i = 0; i < 3; i++) ii = max(ii, {sat[i].size(),i});
int fat = ii.second;
while(sat[0].size() + sat[1].size() + sat[2].size() > 0){
if(prev != fat){
prev = fat;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
else{
ii = {-10,-1};
for(int i = 0; i < 3; i++) if(i != prev && !sat[i].empty())ii = max(ii, {sat[i].begin() -> first,i});
prev = ii.second;
ans.push_back(sat[prev].begin() -> second);
sat[prev].erase(sat[prev].begin());
N--;
}
}
ans.push_back(it);
return ans;
}
}