Submission #394770

#	Time	Username	Problem	Language	Result	Execution time	Memory
394770		idk321	Roller Coaster Railroad (IOI16_railroad)	C++11	0 / 100	218 ms	14952 KiB

railroad

#include "railroad.h"

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

const ll M = 2000000000LL;

int n;
vector<int> s;
vector<int> t;

ll solveFor(vector<int> a, vector<int> b)
{

}

bool  solveCur(int small, int big)
{
    bool cur = true;
    set<array<int, 2>> byS;
    for (int i = 0; i < n; i++)
    {
        if (i != small) byS.insert({s[i], i});
    }

    for (int i = 0; i < n; i++)
    {
        if (i != big && i != small)
        {
            auto it = byS.lower_bound({t[i], 0});
            if (it != byS.end() && (*it)[1] == i) it++;
            if (it == byS.end())
            {
                cur = false;
            } else byS.erase(it);
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (i == small)
        {
            auto it = byS.lower_bound({t[i], 0});
            if (it != byS.end() && (*it)[1] == i) it++;
            if (it == byS.end())
            {
                cur = false;
            } else byS.erase(it);
        }
    }

    return cur;
}

long long plan_roller_coaster(std::vector<int> S, std::vector<int> T) {
    s = S;
    t = T;
    n = (int) s.size();

    bool res = false;


    int big = -1;
    int most = 0;
    for (int i = 0; i < n; i++)
    {
        if (t[i] > most)
        {
            most = t[i];
            big = i;
        }
    }

    int small = -1;
    int least = 2000000000;
    for (int i = 0; i < n; i++)
    {
        if (s[i] < least && i != big)
        {

            least = s[i];
            small = i;
        }
    }


    res = res || solveCur(small, big);

    small = -1;
    least = 2000000000;
    for (int i = 0; i < n; i++)
    {
        if (s[i] < least)
        {
            least = s[i];
            small = i;
        }
    }
    big = -1;
    most = 0;
    for (int i = 0; i < n; i++)
    {
        if (t[i] > most && i != small)
        {
            most = t[i];
            big = i;
        }
    }
    res = res || solveCur(small, big);

    return res;
}

Compilation message (stderr)

railroad.cpp: In function 'll solveFor(std::vector<int>, std::vector<int>)':
railroad.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | }
      | ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36