제출 #1073754

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

longesttrip

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define el '\n'
#define ff first
#define ss second
#define pii pair <ll, ll>
#define pb push_back
#define mkp make_pair
#define fr(i, l, r) for(ll i = l; i <= r; i++)
#define debug(x) \
    { cout << #x << " = " << x << el; }

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

//const ll N = 2e5 + 10;
const ll M = 1e5 + 10;
const ll K = 400;
const ll INF = 1e18 + 10;
const ll inf = 1e9 + 10;
const ll LOG = 20;
const ll mod = 1000002022;
mt19937 rnd(time(0));

bool are_connected(std::vector<int> A, std::vector<int> B);

std::vector<int> longest_trip(int N, int D) {
    vector <int> f, s;
    f.pb(0); s.pb(1);

    vector <int> left;
    fr(i, 2, N - 1)
        left.pb(i);
    shuffle(left.begin(), left.end(), rnd);

    bool ends = 0;
    for(int i : left) {
        bool fir = are_connected({f.back()}, {i});
        if(!ends) {
            bool sec = are_connected({s.back()}, {i});
            if(fir) {
                f.pb(i);
                if(!sec) ends = 1;
            }
            else if(sec) {
                s.pb(i);
                ends = 1;
            }
            else {
                while(!s.empty()) {
                    f.pb(s.back());
                    s.pop_back();
                }
                s.pb(i);
            }
        }
        else {
            ends = 0;
            if(fir)
                f.pb(i);
            else
                s.pb(i);
        }
    }

    if(!are_connected(f, s)) {
        if(f.size() < s.size()) swap(f, s);
        return f;
    }

    vector <int> ans;
    if(f.size() == 1 && are_connected({f[0]}, {s[0], s.back()})) {
        if(are_connected({f[0]}, {s[0]})) {
            ans = f;
            for(int j : s)
                ans.pb(j);
        }
        else {
            ans = s;
            for(int j : f)
                ans.pb(j);
        }
        return ans;
    }
    else if(s.size() == 1 && are_connected({s[0]}, {f[0], f.back()})) {
        if(are_connected({f[0]}, {s[0]})) {
            ans = s;
            for(int j : f)
                ans.pb(j);
        }
        else {
            ans = f;
            for(int j : s)
                ans.pb(j);
        }
        return ans;
    }
    else if(f.size() > 1 && s.size() > 1 && are_connected({f[0], f.back()}, {s[0], s.back()})) {
        if(are_connected({f[0]}, {s[0]})) {
            reverse(f.begin(), f.end());
            ans = f;
            for(int j : s)
                ans.pb(j);
        }
        else if(are_connected({f[0]}, {s.back()})) {
            ans = s;
            for(int j : f)
                ans.pb(j);
        }
        else if(are_connected({f.back()}, {s[0]})) {
            ans = f;
            for(int j : s)
                ans.pb(j);
        }
        else {
            ans = s;
            reverse(f.begin(), f.end());
            for(int j : f)
                ans.pb(j);
        }
        return ans;
    }

    int l = 0, r = f.size() - 1;
    while(l < r) {
        int mid = (l + r) / 2;
        vector <int> v;
        for(int j = 0; j <= mid; j++)
            v.pb(f[j]);
        if(are_connected(v, s)) r = mid;
        else l = mid + 1;
    }

    int l2 = 0, r2 = s.size() - 1;
    while(l2 < r2) {
        int mid = (l2 + r2) / 2;
        vector <int> v, v2;
        for(int j = 0; j <= l; j++)
            v.pb(f[j]);
        for(int j = 0; j <= mid; j++)
            v2.pb(s[j]);
        if(are_connected(v, v2)) r2 = mid;
        else l2 = mid + 1;
    }


    for(int i = l + 1; i < f.size(); i++)
        ans.pb(f[i]);
    for(int i = 0; i <= l; i++)
        ans.pb(f[i]);
    for(int i = l2; i < s.size(); i++)
        ans.pb(s[i]);
    for(int i = 0; i < l2; i++)
        ans.pb(s[i]);

    return ans;
}


/*
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
    printf("Protocol Violation: %s\n", message.c_str());
    exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
    ++call_counter;
    ++total_call_counter;
    if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
    {
        protocol_violation("too many calls");
    }

    int nA = A.size(), nB = B.size();
    landmark_counter += nA + nB;
    if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
    {
        protocol_violation("too many elements");
    }

    if (nA == 0 || nB == 0)
    {
        protocol_violation("invalid array");
    }
    for (int i = 0; i < nA; ++i)
    {
        if (A[i] < 0 || N <= A[i])
        {
            protocol_violation("invalid array");
        }
        if (present[A[i]])
        {
            protocol_violation("invalid array");
        }
        present[A[i]] = true;
    }
    for (int i = 0; i < nA; ++i)
    {
        present[A[i]] = false;
    }
    for (int i = 0; i < nB; ++i)
    {
        if (B[i] < 0 || N <= B[i])
        {
            protocol_violation("invalid array");
        }
        if (present[B[i]])
        {
            protocol_violation("invalid array");
        }
        present[B[i]] = true;
    }
    for (int i = 0; i < nB; ++i)
    {
        present[B[i]] = false;
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (A[i] == B[j])
            {
                protocol_violation("non-disjoint arrays");
            }
        }
    }

    for (int i = 0; i < nA; ++i)
    {
        for (int j = 0; j < nB; ++j)
        {
            if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
            {
                return true;
            }
        }
    }

    return false;
}

int main()
{
    assert(1 == scanf("%d", &C));
    int maximumCalls = 0;
    for (int c = 0; c < C; ++c)
    {
        call_counter = 0;
        assert(2 == scanf("%d %d", &N, &D));

        present.assign(N, false);
        U.resize(N);
        for (int i = 1; i < N; ++i)
        {
            U[i].resize(i);
            for (int j = 0; j < i; ++j)
            {
                assert(1 == scanf("%d", &U[i][j]));
            }
        }

        for (int i = 2; i < N; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                for (int k = 0; k < j; ++k)
                {
                    if (U[i][j] + U[i][k] + U[j][k] < D)
                    {
                        printf("Insufficient Density\n");
                        exit(0);
                    }
                }
            }
        }

        std::vector<int> t = longest_trip(N, D);
        int l = t.size();
        //printf("%d\n", l);
        bool ok = 1;
        for (int i = 0; i < l; ++i)
        {
            if(i) {
                int a = t[i - 1], b = t[i];
                if(a > b) swap(a, b);
                if(!U[b][a]) ok = 0;
            }
            //printf(i == 0 ? "%d" : " %d", t[i]);
        }
        //printf("\n");
        if(!ok) cout << "INVALID" << el;
        //printf("%d\n", call_counter);

        maximumCalls = std::max(maximumCalls, call_counter);
        call_counter = 0;
    }
    //printf("%d\n", maximumCalls);

    return 0;
}
*/

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

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:157:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i = l + 1; i < f.size(); i++)
      |                        ~~^~~~~~~~~~
longesttrip.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |     for(int i = l2; i < s.size(); i++)
      |                     ~~^~~~~~~~~~

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