oj.uz

Submission #883137

# Submission time Handle Problem Language Result Execution time Memory
883137 2023-12-04T15:45:35 Z abcvuitunggio Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 144 ms 10628 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,k,c[200001][4],mn=INF,mx,mn2=INF,mx2,x,y,mask[200001];
vector <pair <int, int>> res;
vector <int> v,ve[16];
vector <pair <int, int>> type[16];
bool check(vector <int> v, int k){
    if (v.empty()){
        while (k--)
            cout << 1 << ' ' << 1 << '\n';
        return true;
    }
    if (!k)
        return false;
    int a[2]={INF,0},b[2]={INF,0};
    for (int i:v){
        a[0]=min(a[0],c[i][2]);
        a[1]=max(a[1],c[i][0]);
        b[0]=min(b[0],c[i][3]);
        b[1]=max(b[1],c[i][1]);
    }
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++){
            vector <int> v2;
            for (int k:v)
                if (c[k][0]>a[i]||c[k][2]<a[i]||c[k][1]>b[j]||c[k][3]<b[j])
                    v2.push_back(k);
            if (check(v2,k-1)){
                cout << a[i] << ' ' << b[j] << '\n';
                return true;
            }
        }
    return false;
}
void strain(int idx, int a, int b, int sign, int dir){
    x=a,y=b;
    sort(ve[idx].begin(),ve[idx].end(),[](int i, int j){
            return make_pair(c[i][x],c[i][y])<make_pair(c[j][x],c[j][y]);
        });
    int mx=-INF;
    for (int i:ve[idx]){
        if (!dir){
            while (!type[idx].empty()&&c[i][y]*sign<type[idx].back().second*sign)
                type[idx].pop_back();
            type[idx].push_back({c[i][x],c[i][y]});
        }
        else if (type[idx].empty()||c[i][y]*sign>type[idx].back().second*sign)
            type[idx].push_back({c[i][x],c[i][y]});
    }
}
int f(int mask, int pos, int pos2=-INF){
    int res=(type[mask].empty()?INF:type[mask][0].second);
    if (!type[6].empty()){
        int tmp=upper_bound(type[6].begin(),type[6].end(),make_pair(pos2,INF))-type[6].begin();
        if (tmp<type[6].size())
            res=min(res,type[6][tmp].second);
    }
    if (!type[mask|1].empty()){
        if (mask==4){
            int tmp=lower_bound(type[5].begin(),type[5].end(),make_pair(pos,0))-type[5].begin()-1;
            if (tmp>=0)
                res=min(res,type[5][tmp].second);
        }
        if (mask==2){
            int tmp=upper_bound(type[3].begin(),type[3].end(),make_pair(pos,0))-type[3].begin();
            if (tmp<type[3].size())
                res=min(res,type[3][tmp].second);
        }
    }
    return res;
}
pair <int, int> calc(int x, int y){
    int l=0,r=INF;
    if (!type[12].empty()){
        int tmp=upper_bound(type[12].begin(),type[12].end(),make_pair(x,INF))-type[12].begin();
        if (tmp<type[12].size())
            r=type[12][tmp].second;
    }
    if (!type[10].empty()){
        int tmp=upper_bound(type[10].begin(),type[10].end(),make_pair(y,INF))-type[10].begin();
        if (tmp<type[10].size())
            l=type[10][tmp].second;
    }
    return {l,r};
}
void check(int pos, int i){
    if (mask[i]%2==0||(!type[1].empty()&&(pos<type[1].back().first||pos>type[1][0].second)))
        return;
    int l=0,r=INF;
    if (!type[8].empty()){
        l=type[8].back().first;
        r=type[8][0].second;
    }
    if (!type[9].empty()){
        if (pos<=type[9][0].second){
            int tmp=upper_bound(type[9].begin(),type[9].end(),make_pair(pos,INF))-type[9].begin();
            if (tmp<type[9].size()){
                l=max(l,type[9].back().first);
                r=min(r,type[9][tmp].second);
            }
        }
        else if (pos>=type[9].back().first){
            int lo=0,hi=type[9].size(),kq=-1;
            while (lo<=hi){
                int mid=(lo+hi)>>1;
                if (type[9][mid].second<pos){
                    r=min(r,type[9][mid].first);
                    kq=mid;
                    lo=mid+1;
                }
                else
                    hi=mid-1;
            }
            if (kq!=-1)
                l=max(l,type[9][0].second);
        }
        else{
            l=max(l,type[9].back().first);
            r=min(r,type[9][0].second);
        }
    }
    int pos2=f(4,pos);
    if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos2)){
        int pos3=f(2,pos,pos2);
        if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos3)){
            if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
                auto [x,y]=calc(pos2,pos3);
                if (max(l,x)<=min(r,y)){
                    cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mn2 << '\n' << pos3 << ' ' << mx2 << '\n' << mx << ' ' << max(l,x);
                    exit(0);
                }
            }
        }
    }
    pos2=f(2,pos);
    if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos2)){
        int pos3=f(4,pos,pos2);
        if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos3)){
            if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
                auto [x,y]=calc(pos3,pos2);
                if (max(l,x)<=min(r,y)){
                    cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mx2 << '\n' << pos3 << ' ' << mn2 << '\n' << mx << ' ' << max(l,x);
                    exit(0);
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k;
    for (int i=0;i<n;i++){
        for (int j=0;j<4;j++)
            cin >> c[i][j];
        v.push_back(i);
    }
    if (check(v,k))
        return 0;
    for (int i=0;i<n;i++){
        mn=min(mn,c[i][2]);
        mx=max(mx,c[i][0]);
        mn2=min(mn2,c[i][3]);
        mx2=max(mx2,c[i][1]);
    }
    for (int i=0;i<n;i++){
        mask[i]=(c[i][0]<=mn)+(c[i][3]>=mx2)*2+(c[i][1]<=mn2)*4+(c[i][2]>=mx)*8;
        if (__builtin_popcount(mask[i])<3)
            ve[mask[i]].push_back(i);
    }
    strain(1,1,3,1,0);
    strain(2,0,2,1,0);
    strain(4,0,2,1,0);
    strain(8,1,3,1,0);
    strain(3,1,2,1,0);
    strain(5,3,2,-1,1);
    strain(10,0,1,-1,0);
    strain(12,0,3,1,0);
    strain(9,1,3,1,0);
    strain(6,0,2,1,0);
    for (int i=0;i<n;i++){
        check(c[i][1],i);
        check(c[i][3],i);
    }
}

Compilation message

hamburg.cpp: In function 'void strain(int, int, int, int, int)':
hamburg.cpp:41:9: warning: unused variable 'mx' [-Wunused-variable]
   41 |     int mx=-INF;
      |         ^~
hamburg.cpp: In function 'int f(int, int, int)':
hamburg.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if (tmp<type[6].size())
      |             ~~~^~~~~~~~~~~~~~~
hamburg.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if (tmp<type[3].size())
      |                 ~~~^~~~~~~~~~~~~~~
hamburg.cpp: In function 'std::pair<int, int> calc(int, int)':
hamburg.cpp:77:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if (tmp<type[12].size())
      |             ~~~^~~~~~~~~~~~~~~~
hamburg.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         if (tmp<type[10].size())
      |             ~~~^~~~~~~~~~~~~~~~
hamburg.cpp: In function 'void check(int, int)':
hamburg.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             if (tmp<type[9].size()){
      |                 ~~~^~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2508 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2532 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2600 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 4 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Incorrect 4 ms 2904 KB Unexpected end of file - int32 expected
21 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 64 ms 5852 KB Output is correct
6 Correct 62 ms 5648 KB Output is correct
7 Correct 71 ms 5832 KB Output is correct
8 Correct 61 ms 5840 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 62 ms 6552 KB Output is correct
6 Correct 69 ms 6512 KB Output is correct
7 Correct 70 ms 6608 KB Output is correct
8 Correct 76 ms 8532 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2508 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2532 KB Output is correct
13 Correct 67 ms 6536 KB Output is correct
14 Correct 64 ms 6700 KB Output is correct
15 Correct 68 ms 6272 KB Output is correct
16 Correct 63 ms 6272 KB Output is correct
17 Correct 72 ms 7020 KB Output is correct
18 Correct 79 ms 6352 KB Output is correct
19 Correct 70 ms 7120 KB Output is correct
20 Correct 73 ms 7988 KB Output is correct
21 Correct 144 ms 10628 KB Output is correct
22 Correct 90 ms 8644 KB Output is correct
23 Correct 90 ms 9536 KB Output is correct
24 Correct 97 ms 10392 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 3 ms 2600 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 4 ms 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Incorrect 4 ms 2904 KB Unexpected end of file - int32 expected
21 Halted 0 ms 0 KB -