Submission #841179

#	Time	Username	Problem	Language	Result	Execution time	Memory
841179		NicolaAbusaad2014	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	89 ms	336 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

void split(vector<int>&v,int sz,vector<int>&a,vector<int>&b)
{
    for(int i=0;i<sz;i++){
        a.push_back(v[i]);
    }
    for(int i=sz;i<v.size();i++){
        b.push_back(v[i]);
    }
}

void BS(vector<int>A,vector<int>B,int&s,int&e)
{
    while(A.size()>1){
        vector<int>a,b;
        split(A,(A.size())/2,a,b);
        if(are_connected(a,B)){
            swap(A,a);
        }
        else{
            swap(A,b);
        }
    }
    while(B.size()>1){
        vector<int>a,b;
        split(B,(B.size())/2,a,b);
        if(are_connected(A,a)){
            swap(B,a);
        }
        else{
            swap(B,b);
        }
    }
    s=A[0];
    e=B[0];
}

std::vector<int> longest_trip(int N, int D)
{
    vector<int>path(1);
    vector<bool>vis(N);
    vis[0]=true;
    while(path.size()<N){
        int a=path.front();
        int b=path.back();
        int c,d;
        vector<int>rest;
        for(int i=0;i<N;i++){
            if(!vis[i]){
                rest.push_back(i);
            }
        }
        if(are_connected(vector<int>(1,a),rest)){
            BS(vector<int>(1,a),rest,c,d);
            path.insert(path.begin(),d);
            vis[d]=true;
            continue;
        }
        if(are_connected(vector<int>(1,b),rest)){
            BS(vector<int>(1,b),rest,c,d);
            path.push_back(d);
            vis[d]=true;
            continue;
        }
        if(!are_connected(path,rest)){
            if(path.size()>=rest.size()){
                return path;
            }
            return rest;
        }
        BS(path,rest,c,d);
        for(int i=0;i<path.size();i++){
            if(path[i]==c){
                c=i;
                break;
            }
        }
        for(int i=0;i<rest.size();i++){
            if(rest[i]==d){
                d=i;
                break;
            }
        }
        vector<int>ans;
        for(int i=c+1;i<path.size();i++){
            ans.push_back(path[i]);
        }
        for(int i=0;i<=c;i++){
            ans.push_back(path[i]);
        }
        for(int i=d;i<rest.size();i++){
            ans.push_back(path[i]);
        }
        for(int i=0;i<d;i++){
            ans.push_back(path[i]);
        }
        return ans;
    }
    return path;
}

Compilation message (stderr)

longesttrip.cpp: In function 'void split(std::vector<int>&, int, std::vector<int>&, std::vector<int>&)':
longesttrip.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=sz;i<v.size();i++){
      |                  ~^~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:47:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while(path.size()<N){
      |           ~~~~~~~~~~~^~
longesttrip.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<path.size();i++){
      |                     ~^~~~~~~~~~~~
longesttrip.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for(int i=0;i<rest.size();i++){
      |                     ~^~~~~~~~~~~~
longesttrip.cpp:89:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int i=c+1;i<path.size();i++){
      |                       ~^~~~~~~~~~~~
longesttrip.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int i=d;i<rest.size();i++){
      |                     ~^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60