oj.uz

Submission #589985

# Submission time Handle Problem Language Result Execution time Memory
589985 2022-07-05T12:53:06 Z marcipan5000 Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 16852 KB 
#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) {
                //cout << d << " true" << endl;
                return(true);
            }
        }
        s1.insert(i);
        s2.insert(i);
    }
    //cout << d << " false" << endl;
    return(false);
}

int log_search(int l,int r) {
    //cout << l << " " << r << endl;
    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));
    }
    //cout << lengths.size() << endl;
    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
*/

/*
5 4
1 -1
2 0
-1 0
0 2
0 -2
*/

Compilation message

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:103:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |     for (;lengths.size()<k;) {
      |           ~~~~~~~~~~~~~~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10035 ms 2504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 16520 KB Output is correct
2 Correct 979 ms 16852 KB Output is correct
3 Execution timed out 10102 ms 2540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10140 KB Output is correct
2 Correct 434 ms 10288 KB Output is correct
3 Execution timed out 10025 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 10140 KB Output is correct
2 Correct 434 ms 10288 KB Output is correct
3 Execution timed out 10025 ms 212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10035 ms 2504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10035 ms 2504 KB Time limit exceeded
2 Halted 0 ms 0 KB -