Submission #1062934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062934		NemanjaSo2005	Rail (IOI14_rail)	C++17	8 / 100	101 ms	98704 KiB

rail

#include "rail.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=5005;
int kesh[maxn][maxn],N,idxC,idxD,poz[maxn],tip[maxn];
vector<pair<int,int>> V;
int dist(int a,int b){
   if(a==b)
      return 0;
   if(kesh[a][b]==-2){
    //  cout<<a<<" - "<<b<<": ";
      int x=getDistance(a,b);
     // cout<<x<<endl;
      kesh[a][b]=kesh[b][a]=x;
   }
   return kesh[a][b];
}
vector<int> C,D;
void findLocation(int n, int first, int location[], int stype[]){
   N=n;
   for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
         kesh[i][j]=-2;
   location[0]=first;
   stype[0]=1;
   if(N==1)
      return;
   for(int i=1;i<N;i++)
      V.push_back({dist(0,i),i});
   sort(V.begin(),V.end());
   idxC=0;
   poz[0]=first;
   tip[0]=1;
   idxD=V[0].s;
   poz[idxD]=first+dist(0,idxD);
   tip[idxD]=2;
   for(int iii=1;iii<V.size();iii++){
      int x=V[iii].s;
      int dc=dist(x,idxC);
      int dd=dist(x,idxD);
      if(min(dc,dd)<dist(idxC,idxD)){
         int dpoz=1e9;
         for(int c:C){ /// Ako je D
            int p1=poz[idxC]+dc;
            int p2=poz[c]+dd-(poz[idxD]-poz[c]);
            if(p1==p2)
               dpoz=-p1;
         }
         for(int d:D){ /// Ako je C
            int p1=poz[d]-(dc-(poz[d]-poz[idxC]));
            int p2=poz[idxD]-dd;
            if(p1==p2)
               dpoz=p1;
         }
         if(dpoz==1e9){
            if(dc<dd)
               dpoz=-(poz[idxC]+dc);
            else
               dpoz=poz[idxD]-dd;
         }
         if(dpoz<0){
            tip[x]=2;
            poz[x]=-dpoz;
         }
         else{
            tip[x]=1;
            poz[x]=dpoz;
         }
      }
      else{
         int dpoz=1e9;
         for(int c:C){ /// Ako je D
            int p1=poz[idxC]+dc;
            int p2=poz[c]+dd-(poz[idxD]-poz[c]);
            if(p1==p2)
               dpoz=-p1;
         }
         for(int d:D){ /// Ako je C
            int p1=poz[d]-(dc-(poz[d]-poz[idxC]));
            int p2=poz[idxD]-dd;
            if(p1==p2)
               dpoz=p1;
         }
         if(dpoz==1e9){
            if(dc<dd)
               dpoz=-(poz[idxC]+dc);
            else
               dpoz=poz[idxD]-dd;
         }
         if(dpoz<0){
            tip[x]=2;
            poz[x]=-dpoz;
         }
         else{
            tip[x]=1;
            poz[x]=dpoz;
         }
      }
      if(tip[x]==1)
         C.push_back(x);
      else
         D.push_back(x);
      if(tip[x]==1 and poz[x]<poz[idxC])
         idxC=x;
      if(tip[x]==2 and poz[x]>poz[idxC])
         idxD=x;
   }
   for(int i=1;i<N;i++){
      location[i]=poz[i];
      stype[i]=tip[i];
   }
}

Compilation message (stderr)

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int iii=1;iii<V.size();iii++){
      |                  ~~~^~~~~~~~~

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