제출 #961661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961661		Prieved1	가장 긴 여행 (IOI23_longesttrip)	C++17	100 / 100	39 ms	4364 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
int cnt=0;
int n;
map<int, map<int,int>> mp;
bool query1(int a, int b) {
  if(mp[a][b]!=0)return mp[a][b]-1;
  int c=are_connected({a}, {b});
  mp[a][b]=c+1;
  mp[b][a]=c+1;
  cnt++;
  return c;
}
bool query2(int a, int b) {
 for(int j  = 0;j<n;j++) {
  if(a==j or j==b)continue;
  if(mp[a][j]==1 and mp[j][b]==1) {
    mp[a][b]=2;
    mp[b][a]=2;
    return 1;
  }
 }
 return query1(a,b);
}
vector<int> longest_trip(int N, int D)
{
  n=N;
  cnt=0;
  mp.clear();
  srand(time(NULL));
  vector<int> id(N);
  iota(id.begin(), id.end(), 0);
  random_shuffle(id.begin(), id.end());
  vector<int> t[2];
  t[0].push_back(id[0]);
  t[1].push_back(id[1]);
  bool connected=1;
  for(int ii = 2;ii<N;ii++) {
    int i=id[ii];
    if(t[0].size() < t[1].size())swap(t[0], t[1]);
    if(t[1].size()>0 and rand()%2) {
      swap(t[0], t[1]);
    }
    if(query2(i, t[0].back())) {
      t[0].push_back(i);
      connected=1;
    }
    else if(connected==false or query2(i, t[1].back())) {
      t[1].push_back(i);
      connected=false;
    }
    else {
      connected=1;
      while(t[1].size()) {
        t[0].push_back(t[1].back());
        t[1].pop_back();
      }
      t[1].push_back(i);
    }
  }
  assert(cnt<380);
  if(t[0].size()<t[1].size())swap(t[0], t[1]);
  if(t[1].size()==0)return t[0];
  if(query2(t[0][0], t[1].back())) {
    reverse(t[0].begin(), t[0].end());
    while(t[1].size()) {
      t[0].push_back(t[1].back());
      t[1].pop_back();
    }
    return t[0];
  }
  if(query2(t[0][0], t[1][0])) {
    reverse(t[0].begin(), t[0].end());
    reverse(t[1].begin(), t[1].end());
    while(t[1].size()) {
      t[0].push_back(t[1].back());
      t[1].pop_back();
    }
    return t[0];
  }
  if(query2(t[0].back(), t[1][0])) {
    reverse(t[1].begin(), t[1].end());
    while(t[1].size()) {
      t[0].push_back(t[1].back());
      t[1].pop_back();
    }
    return t[0];
  }
  if(are_connected(t[0], t[1])==false)return t[0];
  int lo = 0, hi = t[0].size()-1;
  int res=hi;
  while(lo <= hi) {
    int mid=(lo+hi)/2;
    vector<int> tmp;
    for(int j = 0;j<=mid;j++)tmp.push_back(t[0][j]);
    if(are_connected(tmp, t[1])) {
      res=mid;
      hi=mid-1;
    }
    else{
      lo=mid+1;
    }
  }
  lo=0, hi=t[1].size()-1;
  int res2=hi;
  while(lo <= hi) {
    int mid=(lo+hi)/2;
    vector<int> tmp;
    for(int j = 0;j<=mid;j++)tmp.push_back(t[1][j]);
    if(are_connected(tmp, {t[0][res]})) {
      res2=mid;
      hi=mid-1;
    }
    else{
      lo=mid+1;
    }
  }
  vector<int> ans;
  for(int j = res+1;j<t[0].size();j++) {
    ans.push_back(t[0][j]);
  }
  for(int j = 0;j<=res;j++)ans.push_back(t[0][j]);
  for(int j = res2;j<t[1].size();j++)ans.push_back(t[1][j]);
  for(int j = 0;j<res2;j++)ans.push_back(t[1][j]);
  return ans;
}

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

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int j = res+1;j<t[0].size();j++) {
      |                     ~^~~~~~~~~~~~
longesttrip.cpp:124:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int j = res2;j<t[1].size();j++)ans.push_back(t[1][j]);
      |                    ~^~~~~~~~~~~~

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