Submission #1195114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195114		DobromirAngelov	Longest Trip (IOI23_longesttrip)	C++20	100 / 100	5 ms	692 KiB

longesttrip

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

using namespace std;

const int MAXN=260;

mt19937 mt(666);

int n;
vector<int> v;
vector<int> path[2];
int edge[MAXN][MAXN];

bool ask(int x,int y)
{
    if(edge[x][y]==1) return 1;
    if(edge[x][y]==0) return 0;
    if(are_connected({x}, {y})) ///
    {
        edge[x][y]=edge[y][x]=1;
        return 1;
    }
    edge[x][y]=edge[y][x]=0;
    return 0;
}

bool checkEnds()
{
    vector<int> t0={path[0][0], path[0].back()};
    vector<int> t1={path[1][0], path[1].back()};
    if(t0[0]==t0[1]) t0.pop_back();
    if(t1[0]==t1[1]) t1.pop_back();
    if(!are_connected(t0,t1)) return 0;
    // if(t0.size()==1 && t1.size()==1) return 1;
    if(t0.size()==1)
    {
        if(!ask(t0[0], t1[0]))  reverse(path[1].begin(), path[1].end());
        path[0].insert(path[0].end(), path[1].begin(), path[1].end());
        return 1;
    }
    if(t1.size()==1)
    {
        if(!ask(t0.back(), t1[0])) reverse(path[0].begin(), path[0].end());
        path[0].push_back(t1[0]);
        return 1;
    }
    if(are_connected({t0.back()}, t1))
    {
        if(!ask(t0.back(), t1[0])) reverse(path[1].begin(), path[1].end());
        path[0].insert(path[0].end(), path[1].begin(), path[1].end());
        return 1;
    }
    else
    {
        reverse(path[0].begin(), path[0].end());
        if(!ask(t0[0], t1[0])) reverse(path[1].begin(), path[1].end());
        path[0].insert(path[0].end(), path[1].begin(), path[1].end());
        return 1;
    }
}

std::vector<int> longest_trip(int N, int D)
{
    n=N;
    path[0].clear(); path[1].clear();
    v.clear();
    for(int i=0;i<n;i++) v.push_back(i);
    shuffle(v.begin(), v.end(), mt);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++) edge[i][j]=edge[j][i]=-1;
    }
    
    path[0].push_back(v[0]);
    bool fl=0;
    for(int i=1;i<n;i++)
    {
        if(ask(path[0].back(), v[i]))
        {
            path[0].push_back(v[i]);
            fl=0;
            continue;
        }
        if(path[1].empty())
        {
            path[1].push_back(v[i]);
            fl=1;
            continue;
        }
        if(fl)
        {
            path[1].push_back(v[i]);
            fl=1;
            continue;
        }
        if(ask(path[1].back(), v[i]))
        {
            path[1].push_back(v[i]);
            fl=1;
            continue;
        }
        path[0].insert(path[0].end(), path[1].rbegin(), path[1].rend());
        if(path[1].size()==1) fl=1;
        else fl=0;
        path[1].clear();
        path[1].push_back(v[i]);
    }

    if(path[1].empty()) return path[0];

    if(!are_connected(path[0], path[1]))
    {
        if(path[0].size()>=path[1].size()) return path[0];
        else return path[1];
    }
    else
    {
        if(checkEnds()) return path[0];

        int l=0, r=path[0].size();
        while(l<r)
        {
            int mid=(l+r)/2;
            vector<int> tmp(path[0].begin()+l, path[0].begin()+mid+1);
            if(are_connected(tmp, path[1])) r=mid;
            else l=mid+1;
        }
        int ind0=l;
        l=0, r=path[1].size();
        while(l<r)
        {
            int mid=(l+r)/2;
            vector<int> tmp(path[1].begin()+l, path[1].begin()+mid+1);
            if(are_connected({path[0][ind0]}, tmp)) r=mid;
            else l=mid+1;
        }
        int ind1=l;
        vector<int> ret;
        for(int i=ind0-1;i>=0;i--) ret.push_back(path[0][i]);
        for(int i=path[0].size()-1;i>=ind0;i--) ret.push_back(path[0][i]);
        for(int i=ind1;i>=0;i--) ret.push_back(path[1][i]);
        for(int i=path[1].size()-1;i>ind1;i--) ret.push_back(path[1][i]);
        return ret;
    }
}

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