Submission #1063327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063327		andrei_iorgulescu	Rail (IOI14_rail)	C++14	100 / 100	55 ms	740 KiB

rail

#include <bits/stdc++.h>
#include "rail.h"
#warning That's not FB, that's my FB

using namespace std;

int d0[5005];
int d1[5005];
int d;

bool cmp(int x, int y)
{
    return d0[x] < d0[y];
}

void findLocation(int n, int first, int location[], int stype[])
{
    stype[0] = 1;
    location[0] = first;
    for (int i = 1; i < n; i++)
        d0[i] = getDistance(0,i);
    int f, kmin = 1e9;
    for (int i = 1; i < n; i++)
    {
        if (d0[i] < kmin)
            f = i, kmin = d0[i];
    }
    d = kmin;
    stype[f] = 2;
    location[f] = location[0] + kmin;
    for (int i = 1; i < n; i++)
        if (i != f)
            d1[i] = getDistance(f,i);
    vector<int> st,dr;
    for (int i = 1; i < n; i++)
    {
        if (i != f)
        {
            if (d0[i] < 2 * d and d1[i] < d and d0[i] - d1[i] == d)
            {
                stype[i] = 1;
                location[i] = location[f] - d1[i];
            }
            else if (d1[i] == d0[i] - d)
                st.push_back(i);
            else
                dr.push_back(i);
        }
    }
    sort(st.begin(), st.end(), cmp);
    sort(dr.begin(), dr.end(), cmp);
    vector<int> jos;
    for (auto it : st)
    {
        vector<int> candi, loci;
        for (int i = 0; i < jos.size(); i++)
        {
            int upb;
            if (i == 0)
                upb = location[0] - location[jos[i]];
            else
                upb = location[jos[i - 1]] - location[jos[i]];
            upb--;
            int dsmin = d1[jos[i]] + 1, dsmax = dsmin + upb - 1;
            if (d1[it] >= dsmin and d1[it] <= dsmax)
                candi.push_back(i), loci.push_back(location[jos[i]] + (d1[it] - d1[jos[i]]));
        }
        if (candi.empty())
        {
            stype[it] = 1;
            location[it] = location[f] - d1[it];
            jos.push_back(it);
        }
        else
        {
            int js = jos.back();
            int qr = getDistance(it, js);
            int p2 = location[js] + qr;
            bool yeah = false;
            for (auto itt : loci)
            {
                if (itt == p2)
                {
                    stype[it] = 2;
                    location[it] = p2;
                    yeah = true;
                }
            }
            if (!yeah)
            {
                jos.push_back(it);
                stype[it] = 1;
                location[it] = location[f] - d1[it];
            }
        }
    }

    vector<int> sus;
    for (auto it : dr)
    {
        vector<int> candi, loci;
        for (int i = 0; i < sus.size(); i++)
        {
            int upb;
            if (i == 0)
                upb = location[sus[i]] - location[f];
            else
                upb = location[sus[i]] - location[sus[i - 1]];
            upb--;
            int dsmin = d1[sus[i]] + 1, dsmax = dsmin + upb - 1;
            if (d1[it] >= dsmin and d1[it] <= dsmax)
                candi.push_back(i), loci.push_back(location[sus[i]] - (d1[it] - d1[sus[i]]));
        }
        if (candi.empty())
        {
            stype[it] = 2;
            location[it] = d0[it] + location[0];
            sus.push_back(it);
        }
        else
        {
            int ss = sus.back();
            int qr = getDistance(it, ss);
            int p2 = location[ss] - qr;
            bool yeah = false;
            for (auto itt : loci)
            {
                if (itt == p2)
                {
                    stype[it] = 1;
                    location[it] = p2;
                    yeah = true;
                }
            }
            if (!yeah)
            {
                sus.push_back(it);
                stype[it] = 2;
                location[it] = location[0] + d0[it];
            }
        }
    }
    //for (int i = 0; i < n; i++)
      //  cout << stype[i] << ' ' << location[i] << endl;
}

/**
d(i,j) = d(j,i) ofc
Iau toate d(0,i) -> d(i); gasesc aia minima, o sa fie prima D in dreapta, fie ea p, si fie d = d(p)
Iau toate d(p,i) -> d2(i); pentru fiecare i != 0 si i != p, e usor de aflat din astea daca e cumva intre 0 si p (si chiar pozitia lui), tipul fiind C
In plus, pentru alea aflate in stanga lui 0, d2(i) o sa fie d1(i) - d, iar daca o sa fie in dreapta, d2(i) o sa fie strict mai mare ca d1(i) - d
Acum, departajand in stanga, fac o chestie dubioasa de le iau crescator, am doua variante (ori un C nou in stanga de tot, ori un D pe undeva stabilit)
Intre alea doua variante stabilesc cu inca un query de distanta
Cred ca ceva de genul ar trebui sa iasa si in dreapta si raman in N - 1 + N - 2 + N - 2 = maxim 3N - 5 query-uri
Sunt bot but it can be fixed
**/

Compilation message (stderr)

rail.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < jos.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < sus.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:29:11: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     stype[f] = 2;
      |           ^

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44