Submission #589969

#	Time	Username	Problem	Language	Result	Execution time	Memory
589969		marcipan5000	Road Construction (JOI21_road_construction)	C++14	0 / 100	729 ms	18552 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

struct pont{
    int x,y;
    int s;
};

struct par{
    int a,b;
};

struct classcomp1{
    bool operator() (pont x,pont y) {
        return((x.x<y.x)||((x.x==y.x)&&(x.s<y.s)));
    }
};

struct classcomp2{
    bool operator() (pont x,pont y) {
        return((x.y<y.y)||((x.y==y.y)&&(x.s<y.s)));
    }
};

bool kis(pont x,pont y) {
    return((x.y<y.y)||((x.y==y.y)&&(x.x<y.x)));
};

int n,k;
int x,y;
vector<pont> t;
vector<pont> orig;
vector<pont> t2;
pont z;
vector<par> cur,ma;
par q;
set<pont,classcomp1> s1;
set<pont,classcomp1>::iterator it1;
set<pont,classcomp2> s2;
set<pont,classcomp2>::iterator it2;

bool exist(int d) {
    cur.clear(); s1.clear(); s2.clear();
    for (pont i:t2) {
        //cout << d << " " << i.s << endl;
        while ((s2.size()>0)&&((*s2.begin()).y<i.y-d)) {
            //cout << d << " " << i.s << " erase: " << (*s2.begin()).s << endl;
            s1.erase((*s2.begin()));
            s2.erase(s2.begin());
        }
        z=i; z.x-=d; z.s=-1;
        for (it1=s1.lower_bound(z);(it1!=s1.end())&&((*it1).x<=i.x+d);it1++) {
            //cout << d << " " << i.s << " found: " << (*it1).s << endl;
            q.a=i.s; q.b=(*it1).s;
            cur.push_back(q);
            if (cur.size()>=k) {
                return(true);
            }
        }
        s1.insert(i);
        s2.insert(i);
    }
    return(false);
}

int log_search(int l,int r) {
    if (l==r) {
        return(l);
    }
    if (exist((l+r)/2)+1) {
        ma=cur;
        return(log_search(l,(l+r)/2));
    } else {
        return(log_search((l+r)/2+1,r));
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for (int i=0;i<n;i++) {
        cin >> x >> y;
        z.x=x+y; z.y=x-y; z.s=i;
        t.push_back(z);
        z.x=x; z.y=y; z.s=i;
        orig.push_back(z);
    }
    t2=t;
    sort(t2.begin(),t2.end(),kis);
    int ans=log_search(1,2e9);
    exist(ans);
    vector<int> lengths; lengths.clear();
    for (par i:cur) {
        lengths.push_back(abs(orig[i.a].x-orig[i.b].x)+abs(orig[i.a].y-orig[i.b].y));
    }

    for (;lengths.size()<k;) {
        lengths.push_back(ans+1);
    }
    sort(lengths.begin(),lengths.end());
    for (int i:lengths) {
        cout << i << endl;
    }

    return 0;
}

/*
3 2
-1 0
0 2
0 0
*/

Compilation message (stderr)

road_construction.cpp: In function 'bool exist(int)':
road_construction.cpp:57:27: warning: comparison of integer expressions of different signedness: 'std::vector<par>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |             if (cur.size()>=k) {
      |                 ~~~~~~~~~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:100:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     for (;lengths.size()<k;) {
      |           ~~~~~~~~~~~~~~^~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35