Submission #430773

#	Time	Username	Problem	Language	Result	Execution time	Memory
430773		Amylopectin	Rail (IOI14_rail)	C++14	100 / 100	100 ms	580 KiB

rail

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include "rail.h"
//#include "grader.cpp"
using namespace std;
const int mxn = 5010,mxi = 1e9 + 10;
struct we
{
    int ind,dis;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.dis < r.dis;
}
struct we le[mxn] = {},ri[mxn] = {};
int fr0[mxn] = {},frc[mxn] = {},lli[mxn] = {},rli[mxn] = {};
void findLocation(int n, int stn, int aloc[], int asty[])
{
    int i,j,cmi = mxi,cn = -1,rul = 0,rur = 0,col = 0,cor = 0,cl,cr,mid,cva,cdif,cpo;
    for(i=1; i<n; i++)
    {
        fr0[i] = getDistance(0,i);
        if(fr0[i] < cmi)
        {
            cmi = fr0[i];
            cn = i;
        }
    }
    for(i=1; i<n; i++)
    {
        if(i != cn)
        {
            frc[i] = getDistance(cn,i);
            if(fr0[i] - frc[i] != cmi)
            {
                ri[rur] = {i,fr0[i]};
                rur ++;
            }
            else
            {
                le[rul] = {i,frc[i]};
                rul ++;
            }
        }
    }
    aloc[0] = stn;
    asty[0] = 1;
    aloc[cn] = stn + fr0[cn];
    asty[cn] = 2;
    sort(le,le+rul,cmp);
    sort(ri,ri+rur,cmp);
    if(rul > 0)
    {
        while(le[col].dis < cmi && col < rul-1)
        {
            lli[col] = le[col].ind;
            aloc[lli[col]] = aloc[cn] - le[col].dis;
            asty[lli[col]] = 1;
            col ++;
        }
        lli[col] = le[col].ind;
        aloc[lli[col]] = aloc[cn] - le[col].dis;
        asty[lli[col]] = 1;
        col ++;
    }
    for(i=col; i<rul; i++)
    {
        cpo = aloc[lli[col-1]] + getDistance(lli[col-1],le[i].ind);
        cl = 0;
        cr = col-1;
        while(cl < cr)
        {
            mid = (cl+cr) / 2;
            if(aloc[lli[mid]] <= cpo)
            {
                cr = mid;
            }
            else
            {
                cl = mid+1;
            }
        }
        if(aloc[cn] - aloc[lli[cl]] + cpo - aloc[lli[cl]] == le[i].dis && cpo < aloc[0])
        {
            aloc[le[i].ind] = cpo;
            asty[le[i].ind] = 2;
        }
        else
        {
            aloc[le[i].ind] = aloc[cn] - le[i].dis;
            asty[le[i].ind] = 1;
            lli[col] = le[i].ind;
            col ++;
        }
    }
    if(rur > 0)
    {
        rli[0] = ri[0].ind;
        aloc[rli[0]] = aloc[0] + ri[0].dis;
        asty[rli[0]] = 2;
        cor ++;
    }

    for(i=1; i<rur; i++)
    {
        cpo = aloc[rli[cor-1]] - getDistance(rli[cor-1],ri[i].ind);
        cl = 0;
        cr = cor-1;
        while(cl < cr)
        {
            mid = (cl+cr) / 2;
            if(aloc[rli[mid]] < cpo)
            {
                cl = mid + 1;
            }
            else
            {
                cr = mid;
            }
        }
        if(aloc[rli[cl]] * 2 - aloc[0] - cpo == ri[i].dis && cpo > aloc[cn])
        {
            aloc[ri[i].ind] = cpo;
            asty[ri[i].ind] = 1;
        }
        else
        {
            aloc[ri[i].ind] = aloc[0] + ri[i].dis;
            asty[ri[i].ind] = 2;
            rli[cor] = ri[i].ind;
            cor ++;
        }
    }
//    for(i=0; i<n; i++)
//    {
//        printf("for %d : %d %d\n",i,aloc[i],asty[i]);
//    }
    return ;
}
//int main()
//{
//    cout << "Hello world!" << endl;
//    return 0;
//}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:20:11: warning: unused variable 'j' [-Wunused-variable]
   20 |     int i,j,cmi = mxi,cn = -1,rul = 0,rur = 0,col = 0,cor = 0,cl,cr,mid,cva,cdif,cpo;
      |           ^
rail.cpp:20:73: warning: unused variable 'cva' [-Wunused-variable]
   20 |     int i,j,cmi = mxi,cn = -1,rul = 0,rur = 0,col = 0,cor = 0,cl,cr,mid,cva,cdif,cpo;
      |                                                                         ^~~
rail.cpp:20:77: warning: unused variable 'cdif' [-Wunused-variable]
   20 |     int i,j,cmi = mxi,cn = -1,rul = 0,rur = 0,col = 0,cor = 0,cl,cr,mid,cva,cdif,cpo;
      |                                                                             ^~~~

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