제출 #841335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841335		NicolaAbusaad2014	가장 긴 여행 (IOI23_longesttrip)	C++17	85 / 100	21 ms	476 KiB

longesttrip

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

using namespace std;
#define all(x) x.begin(),x.end()

vector<int>join(vector<int>&A,vector<int>&B)
{
    vector<int>ret=A;
    for(int i=0;i<B.size();i++){
        ret.push_back(B[i]);
    }
    return ret;
}

bool are_connected(int a,int b)
{
    return are_connected(vector<int>(1,a),vector<int>(1,b));
}

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<vector<int> >path(N);
    for(int i=0;i<N;i++){
        path[i].push_back(i);
    }
    while(path.size()>2){
        int sz=path.size();
        vector<int>A=path[sz-1],B=path[sz-2],C=path[sz-3];
        if(are_connected(A.back(),B[0])){
            path.pop_back();
            path.pop_back();
            path.push_back(join(A,B));
            continue;
        }
        if(are_connected(A.back(),C[0])){
            path.pop_back();
            path.pop_back();
            path.pop_back();
            path.push_back(join(A,C));
            path.push_back(B);
            continue;
        }
        path.pop_back();
        path.pop_back();
        path.pop_back();
        path.push_back(A);
        reverse(all(B));
        path.push_back(join(B,C));
    }
    if(are_connected(path[0][0],path[1][0])){
        reverse(all(path[0]));
        return join(path[0],path[1]);
    }
    if(are_connected(path[0][0],path[1].back())){
        return join(path[1],path[0]);
    }
    if(are_connected(path[0].back(),path[1][0])){
        return join(path[0],path[1]);
    }
    if(are_connected(path[0].back(),path[1].back())){
        reverse(all(path[1]));
        return join(path[0],path[1]);
    }
    if(!are_connected(path[0],path[1])){
        if(path[0].size()>=path[1].size()){
            return path[0];
        }
        return path[1];
    }
    int c,d;
    BS(path[0],path[1],c,d);
    for(int i=0;i<path[0].size();i++){
        if(path[0][i]==c){
            c=i;
            break;
        }
    }
    for(int i=0;i<path[1].size();i++){
        if(path[1][i]==d){
            d=i;
            break;
        }
    }
    vector<int>ans;
    for(int i=c+1;i<path[0].size();i++){
        ans.push_back(path[0][i]);
    }
    for(int i=0;i<=c;i++){
        ans.push_back(path[0][i]);
    }
    for(int i=d;i<path[1].size();i++){
        ans.push_back(path[1][i]);
    }
    for(int i=0;i<d;i++){
        ans.push_back(path[1][i]);
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> join(std::vector<int>&, std::vector<int>&)':
longesttrip.cpp:10:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(int i=0;i<B.size();i++){
      |                 ~^~~~~~~~~
longesttrip.cpp: In function 'void split(std::vector<int>&, int, std::vector<int>&, std::vector<int>&)':
longesttrip.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=sz;i<v.size();i++){
      |                  ~^~~~~~~~~
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i=0;i<path[0].size();i++){
      |                 ~^~~~~~~~~~~~~~~
longesttrip.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i=0;i<path[1].size();i++){
      |                 ~^~~~~~~~~~~~~~~
longesttrip.cpp:121:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int i=c+1;i<path[0].size();i++){
      |                   ~^~~~~~~~~~~~~~~
longesttrip.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=d;i<path[1].size();i++){
      |                 ~^~~~~~~~~~~~~~~

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