제출 #171496

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171496		Ruxandra985	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	11 ms	9720 KiB

bridge

/// doar un caz pentru ca e tarziu:)
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
vector <int> vmax[2*DIMN] , vmin[2*DIMN];
set <int> s;
pair <int,int> nv[DIMN];
int p[2*DIMN];
int findd (int x , int tot){
    int st , dr , mid;

    st = 0;
    dr = tot - 1;

    while (st <= dr){

        mid = (st + dr)/2;
        if (p[mid] == x)
            return mid;
        else if (p[mid] < x)
            st = mid + 1;
        else dr = mid - 1;

    }
    printf ("a");
    return -1;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int k , n , elem , tot = 0 , tot2 = 0, i ,p1 , p2 , left , right , poz;
    char c1 , c2;
    long long sol , base , sl , sr;
    fscanf (fin,"%d%d\n",&k,&n);
    base = 0;
    elem = 0;
    for (i=1;i<=n;i++){
        c1 = fgetc(fin);
        fscanf (fin,"%d ",&p1);
        c2 = fgetc(fin);
        fscanf (fin,"%d\n",&p2);
        if (c1 == c2){
            base = base + max ( p2 - p1 , p1 - p2 );
        }
        else{
            base = base + 1 + max ( p2 - p1 , p1 - p2 );

            nv[++elem] = make_pair(min(p1,p2) , max(p1,p2));
            p[tot++] = p1;
            p[tot++] = p2;

        }
    }
    sort ( p , p + tot);
    tot2 = 0;
    for (i=0;i<tot;i++){
        if (i == 0 || p[i] != p[i-1])
            p[tot2++] = p[i];
    }
    tot = tot2;
    for (i=1;i<=elem;i++){

        nv[i].first = findd (nv[i].first , tot);
        nv[i].second = findd (nv[i].second , tot);

        p1 = nv[i].first;
        p2 = nv[i].second;
        s.insert(p1);
        s.insert(p2);
        vmax[max(p1 ,p2)].push_back(min(p1 , p2));
        vmin[min(p1 ,p2)].push_back(max(p1 , p2));

    }
    n = elem;
    sort (nv + 1 , nv + elem + 1);
    if (k == 1){
        left = 0;
        right = n - vmin[*(s.begin())].size();
        sl = 0;
        sr = 0;
        for (i=1;i<=n;i++){
            if (nv[i].first != *(s.begin()))
                sr = sr + 2 * p[nv[i].first] - 2 * p[(*(s.begin()))];
        }
        sol = 2000000000;
        for (set <int> :: iterator it = s.begin() ; it != s.end() ;){

            poz = (*it);
           // printf ("%d ",poz);
            sol = min(sol , sl + sr);

            /// acum e timpul sa modific left ul si right ul

            left = left + vmax[poz].size();
            right = right - vmin[poz+1].size();

            it++;
            if (it == s.end())
                break;

            sl += 2 * (p[(*it)] - p[poz]) * left;
            sr -= 2 * (p[(*it)] - p[poz]) * ( right + vmin[poz+1].size() );

        }
        fprintf (fout,"%lld" , sol + base);
    }
    else {

    }
    return 0;
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:36:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d\n",&k,&n);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
bridge.cpp:41:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d ",&p1);
         ~~~~~~~^~~~~~~~~~~~~~~
bridge.cpp:43:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d\n",&p2);
         ~~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37