Submission #290385

#	Time	Username	Problem	Language	Result	Execution time	Memory
290385		beso123	Fun Tour (APIO20_fun)	C++14	31 / 100	153 ms	19164 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
vector<int> get_pas(set<pii> s1,set<pii> s2){
    vector<int> ans;
    int d=1;
if(s2.size()>s1.size())
    d=2;
while(true){
        pii v;
    if(d==1){
        v=*s1.begin();
        s1.erase(s1.begin());
        ans.push_back(v.y);
    }
    else{
               v=*s2.begin();
        s2.erase(s2.begin());
        ans.push_back(v.y);
    }
    d=3-d;
    if(s1.size()==0 && s2.size()==0)
        break;
}
return ans;
}
vector<int> off(set<pii> s1,set<pii> s2,set<pii> s3,int d){
   set<pii>::iterator it;
   for(it=s2.begin();it!=s2.end();it++){
    s1.insert(*it);
   }
   if(d!=-1)
   return get_pas(s3,s1);
   else return get_pas(s1,s3);
}
vector<int> createFunTour(int n,int Q1){
    if(n==2){
        return {0,1};
    }
int cnt=0,csize=INT_MAX;
for(int k=1;k<n;k++){
    int Size=attractionsBehind(0,k);
    if((Size-1)>=(n/2)){
        if(Size<csize){
            csize=Size;
            cnt=k;
        }
    }
}
vector<int> dist(n,0);
vector<int> P,al,ss(n,0);
for(int k=0;k<n;k++){
    if(k==cnt)
        continue;
al.push_back(k);
    dist[k]=hoursRequired(k,cnt);
    if(dist[k]==1)
        P.push_back(k);
}
set<pii> s1,s2,s3;
for(int k=0;k<al.size();k++){
    int a=al[k];
    if(dist[a]==hoursRequired(P[0],a)+1){
            al[k]++;
        al[k]*=-1;
        ss[a]=1;
        s1.insert({-dist[a],a});
    }
}
for(int k=0;k<al.size();k++){
        if(al[k]<0)
        continue;
    int a=al[k];
    if(dist[a]==hoursRequired(P[1],a)+1){
            al[k]++;
        al[k]*=-1;
        ss[a]=2;
        s2.insert({-dist[a],a});
    }
}
if(P.size()!=2){
   for(int k=0;k<al.size();k++){
        if(al[k]<0)
        continue;
    int a=al[k];
    ss[a]=3;
    s3.insert({-dist[a],a});
}
}
set<pii>::iterator it;
vector<int> ans;
vector<int> p;
if(P.size()==2){
    ans=get_pas(s1,s2);
}
else{
    int cur=0;
      while(true){
       int a=s1.size(),b=s2.size(),c=s3.size();
       int ind=0;
       int d=1;
   if(a+b==c){
 
        if(cur==3)
        d=-1;
   ind=1;
   }
      if(c+b==a){
           int d=1;
        if(cur==1)
        d=-1;
  ind=2;
   }
      if(a+c==b){
           int d=1;
        if(cur==2)
        d=-1;
   ind=3;
   }
 
    pii v1=*s1.begin(),v2=*s2.begin(),v3=*s3.begin();
    if(cur==1)
        v1.x=1;
    if(cur==2)
        v2.x=1;
    if(cur==3)
        v3.x=1;
    int mn=min(v1.x,min(v2.x,v3.x));
    if(mn==v1.x){
        ans.push_back(v1.y);
        cur=1;
        s1.erase(s1.begin());
    }
    else
        if(mn==v2.x){
        ans.push_back(v2.y);
        cur=2;
        s2.erase(s2.begin());
    }
    else
        if(mn==v3.x){
        ans.push_back(v3.y);
        cur=3;
        s3.erase(s3.begin());
    }
    if(ind==1){
        p=off(s1,s2,s3,d);
        break;
    }
    if(ind==2){
      p=  off(s3,s2,s1,d);
        break;
    }
        if(ind==3){
      p=  off(s1,s3,s2,d);
        break;
    }
    }
 
}
for(int k=0;k<p.size();k++)
    ans.push_back(p[k]);
ans.push_back(cnt);
return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 | for(int k=0;k<al.size();k++){
      |             ~^~~~~~~~~~
fun.cpp:73:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 | for(int k=0;k<al.size();k++){
      |             ~^~~~~~~~~~
fun.cpp:85:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int k=0;k<al.size();k++){
      |                ~^~~~~~~~~~
fun.cpp:112:16: warning: variable 'd' set but not used [-Wunused-but-set-variable]
  112 |            int d=1;
      |                ^
fun.cpp:118:16: warning: variable 'd' set but not used [-Wunused-but-set-variable]
  118 |            int d=1;
      |                ^
fun.cpp:164:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 | for(int k=0;k<p.size();k++)
      |             ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34