제출 #588237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
588237		FatihSolak	Rail (IOI14_rail)	C++17	30 / 100	98 ms	24396 KiB

rail

    #include "rail.h"
    #include <bits/stdc++.h>
    #define N 5005
    using namespace std;
    int d[N][N];
    int get(int i,int j){
        if(i > j)swap(i,j);
        if(i == j)return 0;
        if(d[i][j])
            return d[i][j];
        return d[i][j] = getDistance(i,j);
    }
    void findLocation(int n, int first, int location[], int stype[])
    {
        for(int i = 0;i<n;i++){
            location[i] = -1;
            stype[i] = -1;
        }
        location[0] = first;
        stype[0] = 1;
        if(n == 1)return;
        vector<pair<int,int>> v;
        for(int i = 0;i<n;i++){
            if(i == 0)continue;
            v.push_back({get(0,i),i});
        }
        sort(v.begin(),v.end());
        int last = v[0].second;
        int x = last;
        location[v[0].second] = get(0,v[0].second) + first;
        stype[v[0].second] = 2;
        set<int> points = {location[last]};
        for(int i = 1;i<v.size();i++){
            //cout << v[i].second << endl;
            if(get(0,v[i].second) > 2*get(0,x) && get(0,v[i].second) > get(x,v[i].second))
                continue;
            int nwpoint = location[last] - get(last, v[i].second);
            int rval = *points.lower_bound(nwpoint);
            //cout << nwpoint << " " << rval << endl;
            if(2*rval - nwpoint - first == get(0,v[i].second)){
                location[v[i].second] = nwpoint;
                stype[v[i].second] = 1;
            }
            else{
                location[v[i].second] = get(0,v[i].second) + first;
                stype[v[i].second] = 2;
                last = v[i].second;
                points.insert(location[last]);
            }
        } 
        vector<pair<int,int>> nw;
        for(auto u:v){
            if(stype[u.second] == -1)
                nw.push_back(u);
        }
        v = nw;
        // cout << endl;
        // for(int i = 0;i<n;i++){
        //     cout << stype[i] << " " << location[i] << endl;
        // }
        // cout << endl;
        if(v.empty())return;
        int frst = v[0].second;
        int y = 0;
        location[v[0].second] =  first - (get(0,v[0].second) - 2*get(0,x));
        stype[v[0].second] = 1;
        points = {location[frst]};
        for(int i = 1;i<v.size();i++){
            // cout << i << "  x " << v[i].second << endl;
            // for(auto u:points){
            //     cout << u << " ";
            // }
            // cout << endl;
            int nwpoint = get(frst, v[i].second) + location[frst];
            int lval = *prev(points.upper_bound(nwpoint));
            // cout << nwpoint << " " << lval << endl;
            // cout <<  get(0,v[i].second) << endl;
            if(-2*lval + nwpoint + 2*location[x] -first == get(0,v[i].second)){
                location[v[i].second] = nwpoint;
                stype[v[i].second] = 2;
            }
            else{
                location[v[i].second] = first - (get(0,v[i].second) - 2*get(0,x)) ;
                stype[v[i].second] = 1;
                frst = v[i].second;
                points.insert(location[frst]);
            }
        } 
     
        // for(int i = 0;i<n;i++){
        //     cout << stype[i] << " " << location[i] << endl;
        // }
        // cout << endl;
     
    }

컴파일 시 표준 에러 (stderr) 메시지

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for(int i = 1;i<v.size();i++){
      |                       ~^~~~~~~~~
rail.cpp:68:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i = 1;i<v.size();i++){
      |                       ~^~~~~~~~~
rail.cpp:64:13: warning: unused variable 'y' [-Wunused-variable]
   64 |         int y = 0;
      |             ^

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