Submission #1063245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063245		andrei_iorgulescu	Rail (IOI14_rail)	C++14	30 / 100	51 ms	928 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;
    vector<int> cn_jos;
    for (auto it : st)
    {
        int candi = -1;
        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 = i;
        }
        if (candi == -1)
        {
            stype[it] = 1;
            location[it] = location[f] - d1[it];
            jos.push_back(it);
            cn_jos.push_back(-1);
        }
        else
        {
            int loc1 = location[f] - d1[it], loc2 = location[jos[candi]] + (d1[it] - d1[jos[candi]]);
            ///ori e loc1 si in jos, ori e loc2 si in sus
            if (cn_jos[candi] == -1)
            {
                int qq = getDistance(it, jos[candi]);
                if (qq == loc2 - location[jos[candi]])
                {
                    cn_jos[candi] = it;
                    stype[it] = 2;
                    location[it] = loc2;
                }
                else
                {
                    stype[it] = 1;
                    location[it] = location[f] - d1[it];
                    jos.push_back(it);
                    cn_jos.push_back(-1);
                }
            }
            else
            {
                int B = location[cn_jos[candi]] - location[jos[candi]];
                if (location[jos[candi]] - loc1 == loc2 - location[jos[candi]])
                {
                    int qq = getDistance(it, jos[candi]);
                    if (qq == loc2 - location[jos[candi]])
                    {
                        stype[it] = 2;
                        location[it] = loc2;
                    }
                    else
                    {
                        stype[it] = 1;
                        location[it] = location[f] - d1[it];
                        jos.push_back(it);
                        cn_jos.push_back(-1);
                    }
                }
                else
                {
                    int qq = getDistance(it, cn_jos[candi]);
                    if (qq == location[cn_jos[candi]] - loc1)
                    {
                        stype[it] = 1;
                        location[it] = loc1;
                        jos.push_back(it);
                        cn_jos.push_back(-1);
                    }
                    else
                    {
                        stype[it] = 2;
                        location[it] = loc2;
                    }
                }
            }
        }
    }

    vector<int> sus;
    vector<int> cn_sus;
    for (auto it : dr)
    {
        int candi = -1;
        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 = i;
        }
        if (candi == -1)
        {
            stype[it] = 2;
            location[it] = d0[it] + location[0];
            sus.push_back(it);
            cn_sus.push_back(-1);
        }
        else
        {
            int loc1 = location[0] + d0[it], loc2 = location[sus[candi]] - (d1[it] - d1[sus[candi]]);
            if (cn_sus[candi] == -1)
            {
                int qq = getDistance(it, sus[candi]);
                if (qq == location[sus[candi]] - loc2)
                {
                    cn_sus[candi] = it;
                    stype[it] = 1;
                    location[it] = loc2;
                }
                else
                {
                    location[it] = loc1;
                    stype[it] = 2;
                    sus.push_back(it);
                    cn_sus.push_back(-1);
                }
            }
            else
            {
                int B = location[sus[candi]] - location[cn_sus[candi]];
                if (loc1 - location[sus[candi]] == location[sus[candi]] - loc2)
                {
                    int qq = getDistance(it, sus[candi]);
                    if (qq == location[sus[candi]] - loc2)
                    {
                        stype[it] = 1;
                        location[it] = loc2;
                    }
                    else
                    {
                        stype[it] = 2;
                        location[it] = loc1;
                        sus.push_back(it);
                        cn_sus.push_back(-1);
                    }
                }
                else
                {
                    int qq = getDistance(it, cn_sus[candi]);
                    if (qq == loc1 - location[cn_sus[candi]])
                    {
                        stype[it] = 2;
                        location[it] = loc1;
                        sus.push_back(it);
                        cn_sus.push_back(-1);
                    }
                    else
                    {
                        stype[it] = 1;
                        location[it] = loc2;
                    }
                }
            }
        }
    }
    //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
**/

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:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i < jos.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:99:21: warning: unused variable 'B' [-Wunused-variable]
   99 |                 int B = location[cn_jos[candi]] - location[jos[candi]];
      |                     ^
rail.cpp:141:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for (int i = 0; i < sus.size(); i++)
      |                         ~~^~~~~~~~~~~~
rail.cpp:182:21: warning: unused variable 'B' [-Wunused-variable]
  182 |                 int B = location[sus[candi]] - location[cn_sus[candi]];
      |                     ^
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: 0 / 26
• Subtask 4: 0 / 44