Submission #652746

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
652746	2022-10-24T06:42:10 Z	XCAC197	Hamburg Steak (JOI20_hamburg)	C++14	15 / 100	225 ms	81168 KB

hamburg

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <assert.h>

#define maxn 2000000
using namespace std;







int low [maxn];
int dfn [maxn];
bool instack [maxn];
stack <int> s;
vector <int> edgs [maxn];
int sccid [maxn];
int t = 0;
int sccct = 0;
int n;
 
void dfs(int u){
    low[u] = ++t;
    dfn[u] = t;
    s.push(u);
    instack[u] = true;
    for(int i = 0; i < edgs[u].size(); i++){
        if(dfn[edgs[u][i]] == 0){
            dfs(edgs[u][i]);
            low[u] = min(low[edgs[u][i]], low[u]);
        }else if(instack[edgs[u][i]]){
            low[u] = min(low[u], dfn[edgs[u][i]]);
        }
    }
    if(low[u] == dfn[u]){
        ++sccct;
        while(!s.empty()){
            int x = s.top();
            sccid[x] = sccct;
            s.pop();
            instack[x] = false;
            if(x == u){
                break;
            }
        }
    }
    
}
 
int neg(int x){
    if(x <= n){
        return x + n;
    }else{
        return x - n;
    }
}












struct rect{
    int l, r, d, u;
    rect(int lin, int rin, int din, int uin){
        l = lin;
        r = rin;
        d = din;
        u = uin;
    }
};

struct point{
    int x, y;
    point(int xin, int yin){
        x = xin;
        y = yin;
    }
};

bool in(point p, rect r){
    return (r.l <= p.x && p.x <= r.r && r.d <= p.y && p.y <= r.u);
}

vector <rect> removeSkewered(vector <rect> v, point p){
    vector <rect> vv;
    for(int i = 0; i < v.size(); i++){
        if(!in(p, v[i])){
            vv.push_back(v[i]);
        }
    }
    return vv;
}

vector <point> ans;

bool solveCorners(vector <rect> v, int k){
    if(k == 0){
        if(v.size() != 0){
            return false;
        }else{
            return true;
        }
    }else{
        if(v.size() != 0){
            int maxL = 1;
            int minR = 1e9;
            int maxD = 1;
            int minU = 1e9;
            for(int i = 0; i < v.size(); i++){
                maxL = max(maxL, v[i].l);
                minR = min(minR, v[i].r);
                maxD = max(maxD, v[i].d);
                minU = min(minU, v[i].u);
            }
            vector <point> testPoints;
            if(maxL <= minR){
                minR = maxL;
            }
            if(maxD <= minU){
                minU = maxD;
            }
            int possX [2] = {maxL, minR};
            int possY [2] = {maxD, minU};
            int itr1 = 2;
            int itr2 = 2;
            if(possX[0] == possX[1]){
                itr1 = 1;
            }
            if(possY[0] == possY[1]){
                itr2 = 1;
            }
            for(int i = 0; i < itr1; i++){
                for(int j = 0; j < itr2; j++){
                    if(solveCorners(removeSkewered(v, point(possX[i], possY[j])), k-1)){
                        ans.push_back(point(possX[i], possY[j]));
                        return true;
                    }
                }
            }
            return false;
        }else{
            return true;
        }
    }
}

bool solveSides(vector <rect> v){
    int maxL = 1;
    int minR = 1e9;
    int maxD = 1;
    int minU = 1e9;
    for(int i = 0; i < v.size(); i++){
        maxL = max(maxL, v[i].l);
        minR = min(minR, v[i].r);
        maxD = max(maxD, v[i].d);
        minU = min(minU, v[i].u);
    }
   // cout << maxL << " " << minR << " " << maxD << " " << minU << endl;
    if(minR+1 < maxL && minU+1 < maxD){
        map <pair<int,int>, int> mp;
        vector <pair<pair<bool, pair<int,int>>, pair<bool, pair<int,int>>>> edgesList;
        for(int i = 0; i < v.size(); i++){
            int ll = v[i].l;
            int rr = v[i].r;
            int dd = v[i].d;
            int uu = v[i].u;
           // cout << ll << " " << rr << " " << dd << " " << uu << endl;
            if((ll <= minR+1 && maxL-1 <= rr) || (dd <= minU+1 && maxD-1 <= uu)){
                //full side cases (> 3 sides) : do nothing
            }else if(rr < minR || maxL < ll || uu < minU || maxD < dd){
                //outside the rectangle: do nothing
            }else{
                vector <pair<int, pair <int, int>>> inter;
                if(ll <= minR && minR <= rr){
                    if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
                        inter.push_back(make_pair(1, make_pair(max(minU+1, dd), min(maxD-1, uu))));
                    }
                }
                if(ll <= maxL && maxL <= rr){
                    if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
                       // cout << minU+1 << " " << dd << "***" << maxD-1 << " " << uu << endl;
                        inter.push_back(make_pair(2, make_pair(max(minU+1, dd), min(maxD-1, uu))));
                    }
                }
                if(dd <= minU && minU <= uu){
                   // cout << "-" << endl;
                    if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
                        inter.push_back(make_pair(3, make_pair(max(minR+1, ll), min(maxL-1, rr))));
                    }
                }
                if(dd <= maxD && maxD <= uu){
                   // cout << "-" << endl;
                    if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
                        inter.push_back(make_pair(4, make_pair(max(minR+1, ll), min(maxL-1, rr))));
                    }
                }
                if(inter.size() >= 3){
                    cout << "??? 190" << endl;
                    return false;
                }else if(inter.size() == 0){
                    //do nothing
                }else if(inter.size() == 1){
                    int side = inter[0].first;
                    int left = inter[0].second.first-1;
                    int right = inter[0].second.second;
                    if(mp.find(make_pair(side,left)) == mp.end()){
                        mp[make_pair(side, left)] = ++n;
                    }
                    if(mp.find(make_pair(side,right)) == mp.end()){
                        mp[make_pair(side, right)] = ++n;
                    }
                 //   cout << i << " " << side << " " << inter[0].second.first << "/" << inter[0].second.second << endl;
                    edgesList.push_back(make_pair(make_pair(true, make_pair(side, left)), make_pair(false, make_pair(side, left))));
                    edgesList.push_back(make_pair(make_pair(false, make_pair(side, right)), make_pair(true, make_pair(side, right))));
                }else{
                    int side0 = inter[0].first;
                    int left0 = inter[0].second.first-1;
                    int right0 = inter[0].second.second;
                    int side1 = inter[1].first;
                    int left1 = inter[1].second.first-1;
                    int right1 = inter[1].second.second;
                    if(mp.find(make_pair(side0,left0)) == mp.end()){
                        mp[make_pair(side0, left0)] = ++n;
                    }
                    if(mp.find(make_pair(side0,right0)) == mp.end()){
                        mp[make_pair(side0, right0)] = ++n;
                    }
                    
                    if(mp.find(make_pair(side1,left1)) == mp.end()){
                        mp[make_pair(side1, left1)] = ++n;
                    }
                    if(mp.find(make_pair(side1,right1)) == mp.end()){
                        mp[make_pair(side1, right1)] = ++n;
                    }
                    edgesList.push_back(make_pair(make_pair(true, make_pair(side0, left0)), make_pair(false, make_pair(side1, left1))));
                    edgesList.push_back(make_pair(make_pair(true, make_pair(side1, left1)), make_pair(false, make_pair(side0, left0))));
                    
                    edgesList.push_back(make_pair(make_pair(false, make_pair(side0, right0)), make_pair(false, make_pair(side1, left1))));
                    edgesList.push_back(make_pair(make_pair(true, make_pair(side1, left1)), make_pair(true, make_pair(side0, right0))));
                    
                    edgesList.push_back(make_pair(make_pair(true, make_pair(side0, left0)), make_pair(true, make_pair(side1, right1))));
                    edgesList.push_back(make_pair(make_pair(false, make_pair(side1, right1)), make_pair(false, make_pair(side0, left0))));
                    
                    edgesList.push_back(make_pair(make_pair(false, make_pair(side0, right0)), make_pair(true, make_pair(side1, right1))));
                    edgesList.push_back(make_pair(make_pair(false, make_pair(side1, right1)), make_pair(true, make_pair(side0, right0))));
                }
                
            }
        }
        if(mp.find(make_pair(1, maxD-1)) == mp.end()){
            mp[make_pair(1, maxD-1)] = ++n;
        }
        edgesList.push_back(make_pair(make_pair(false, make_pair(1, maxD-1)), make_pair(true, make_pair(1, maxD-1))));
        
        if(mp.find(make_pair(2, maxD-1)) == mp.end()){
            mp[make_pair(2, maxD-1)] = ++n;
        }
        edgesList.push_back(make_pair(make_pair(false, make_pair(2, maxD-1)), make_pair(true, make_pair(2, maxD-1))));
        
        if(mp.find(make_pair(3, maxL-1)) == mp.end()){
            mp[make_pair(3, maxL-1)] = ++n;
        }
        edgesList.push_back(make_pair(make_pair(false, make_pair(3, maxL-1)), make_pair(true, make_pair(3, maxL-1))));
        
        if(mp.find(make_pair(4, maxL-1)) == mp.end()){
            mp[make_pair(4, maxL-1)] = ++n;
        }
        edgesList.push_back(make_pair(make_pair(false, make_pair(4, maxL-1)), make_pair(true, make_pair(4, maxL-1))));

        vector <pair<int,int>> sides [4];
        
        int prevSide = 0;
        int prevCord = 0;
        for(auto i = mp.begin(); i != mp.end(); i++){
            pair<pair <int,int>, int> pii = *i;
           // cout << pii.first.first << " " << pii.first.second << " " << pii.second << endl;
            sides[pii.first.first-1].push_back(make_pair(pii.first.second, pii.second));
            if(pii.first.first == prevSide){
                edgesList.push_back(make_pair(make_pair(true, make_pair(prevSide, prevCord)), make_pair(true, pii.first)));
                edgesList.push_back(make_pair(make_pair(false, pii.first), make_pair(false, make_pair(prevSide, prevCord))));
            }
            prevSide = pii.first.first;
            prevCord = pii.first.second;
        }
     //   cout << n << endl;
        for(int i = 0; i < edgesList.size(); i++){
          //  cout << edgesList[i].first.first << " " << edgesList[i].first.second.first << " " << edgesList[i].first.second.second;
           // cout << " -- ";
         //   cout << edgesList[i].second.first << " " << edgesList[i].second.second.first << " " << edgesList[i].second.second.second;
         //   cout << endl;
            pair<bool,pair<int,int>> v1 = edgesList[i].first;
            pair<bool,pair<int,int>> v2 = edgesList[i].second;
            int v1id = mp[v1.second];
            if(!v1.first){
                v1id = neg(v1id);
            }
            int v2id = mp[v2.second];
            if(!v2.first){
                v2id = neg(v2id);
            }
            edgs[v1id].push_back(v2id);
        }
        for(int i = 1; i <= 2*n; i++){
            if(dfn[i] == 0){
                dfs(i);
            }
        }
        bool pos = true;
        for(int i = 1; i <= n; i++){
           //     cout << sccid[i] << " " << sccid[i+n] << endl;
            if(sccid[i] == sccid[i+n]){
                pos = false;
            }
        }
        if(!pos){
        //    cout << "***" << endl;
            return false;
        }
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < sides[i].size(); j++){
                if(sccid[sides[i][j].second] < sccid[sides[i][j].second+n]){
                   if(i == 0){
                       ans.push_back(point(minR, sides[i][j].first));
                   }else if(i == 1){
                       ans.push_back(point(maxL, sides[i][j].first));
                   }else if(i == 2){
                       ans.push_back(point(sides[i][j].first, minU));
                   }else{
                       ans.push_back(point(sides[i][j].first, maxD));
                   }
                   break;
                }
            }
       //     cout << endl;
        }  
        if(ans.size() != 4){
            assert(0);
            cout << "??? 319" << endl;
            return false;
        }else{
            return true;
        }
    }else{
        return false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector <rect> rectArr;
    for(int i = 0; i < N; i++){
        int ll, rr, dd, uu;
        cin >> ll >> dd >> rr >> uu;
        rectArr.push_back(rect(ll, rr, dd, uu));
    }
    if(solveCorners(rectArr,K)){
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i].x << " " << ans[i].y << endl;
        }
    }else if(K == 4 && solveSides(rectArr)){
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i].x << " " << ans[i].y << endl;
        }
    }else{
        cout << "I GIVE UP GOODBYE" << endl;
    }
    
}

Compilation message

hamburg.cpp: In function 'void dfs(int)':
hamburg.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i = 0; i < edgs[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
hamburg.cpp: In function 'std::vector<rect> removeSkewered(std::vector<rect>, point)':
hamburg.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
hamburg.cpp: In function 'bool solveCorners(std::vector<rect>, int)':
hamburg.cpp:120:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for(int i = 0; i < v.size(); i++){
      |                            ~~^~~~~~~~~~
hamburg.cpp: In function 'bool solveSides(std::vector<rect>)':
hamburg.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
hamburg.cpp:173:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |         for(int i = 0; i < v.size(); i++){
      |                        ~~^~~~~~~~~~
hamburg.cpp:186:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  186 |                     if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
      |                        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:191:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  191 |                     if((minU+1) <= dd && dd <= (maxD-1) || (minU+1) <= uu && uu <= (maxD-1)){
      |                        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:198:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  198 |                     if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
      |                        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:204:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  204 |                     if((minR+1) <= ll && ll <= (maxL-1) || (minR+1) <= rr && rr <= (maxL-1)){
      |                        ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:297:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<bool, std::pair<int, int> >, std::pair<bool, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  297 |         for(int i = 0; i < edgesList.size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~~
hamburg.cpp:331:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  331 |             for(int j = 0; j < sides[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:371:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  371 |         for(int i = 0; i < ans.size(); i++){
      |                        ~~^~~~~~~~~~~~
hamburg.cpp:375:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  375 |         for(int i = 0; i < ans.size(); i++){
      |                        ~~^~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	47444 KB	Output is correct
2	Correct	24 ms	47356 KB	Output is correct
3	Correct	24 ms	47392 KB	Output is correct
4	Correct	23 ms	47428 KB	Output is correct

Subtask #2

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47444 KB	Output is correct
2	Correct	24 ms	47444 KB	Output is correct
3	Correct	26 ms	47464 KB	Output is correct
4	Correct	25 ms	47572 KB	Output is correct

Subtask #3

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	47560 KB	Output is correct
2	Correct	27 ms	47432 KB	Output is correct
3	Correct	25 ms	47436 KB	Output is correct
4	Correct	24 ms	47444 KB	Output is correct
5	Correct	24 ms	47456 KB	Output is correct
6	Correct	24 ms	47440 KB	Output is correct
7	Correct	26 ms	47492 KB	Output is correct
8	Correct	25 ms	47632 KB	Output is correct
9	Correct	26 ms	47436 KB	Output is correct
10	Correct	26 ms	47580 KB	Output is correct
11	Correct	24 ms	47572 KB	Output is correct
12	Correct	27 ms	47516 KB	Output is correct

Subtask #4

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47444 KB	Output is correct
2	Correct	24 ms	47456 KB	Output is correct
3	Correct	26 ms	47444 KB	Output is correct
4	Correct	26 ms	47392 KB	Output is correct
5	Correct	29 ms	47516 KB	Output is correct
6	Correct	25 ms	47436 KB	Output is correct
7	Correct	25 ms	47524 KB	Output is correct
8	Correct	27 ms	47684 KB	Output is correct
9	Correct	29 ms	47600 KB	Output is correct
10	Correct	28 ms	47600 KB	Output is correct
11	Correct	26 ms	47700 KB	Output is correct
12	Correct	26 ms	47512 KB	Output is correct
13	Correct	25 ms	47452 KB	Output is correct
14	Incorrect	29 ms	47952 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	47444 KB	Output is correct
2	Correct	24 ms	47356 KB	Output is correct
3	Correct	24 ms	47392 KB	Output is correct
4	Correct	23 ms	47428 KB	Output is correct
5	Correct	104 ms	57324 KB	Output is correct
6	Correct	106 ms	57424 KB	Output is correct
7	Correct	108 ms	57340 KB	Output is correct
8	Correct	106 ms	57260 KB	Output is correct

Subtask #6

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47444 KB	Output is correct
2	Correct	24 ms	47444 KB	Output is correct
3	Correct	26 ms	47464 KB	Output is correct
4	Correct	25 ms	47572 KB	Output is correct
5	Correct	103 ms	60824 KB	Output is correct
6	Correct	120 ms	64484 KB	Output is correct
7	Correct	108 ms	60656 KB	Output is correct
8	Correct	117 ms	67908 KB	Output is correct

Subtask #7

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	47560 KB	Output is correct
2	Correct	27 ms	47432 KB	Output is correct
3	Correct	25 ms	47436 KB	Output is correct
4	Correct	24 ms	47444 KB	Output is correct
5	Correct	24 ms	47456 KB	Output is correct
6	Correct	24 ms	47440 KB	Output is correct
7	Correct	26 ms	47492 KB	Output is correct
8	Correct	25 ms	47632 KB	Output is correct
9	Correct	26 ms	47436 KB	Output is correct
10	Correct	26 ms	47580 KB	Output is correct
11	Correct	24 ms	47572 KB	Output is correct
12	Correct	27 ms	47516 KB	Output is correct
13	Correct	115 ms	69640 KB	Output is correct
14	Correct	111 ms	69692 KB	Output is correct
15	Correct	110 ms	70036 KB	Output is correct
16	Correct	110 ms	67832 KB	Output is correct
17	Correct	113 ms	68668 KB	Output is correct
18	Correct	110 ms	66832 KB	Output is correct
19	Correct	118 ms	70512 KB	Output is correct
20	Correct	225 ms	81168 KB	Output is correct
21	Correct	116 ms	71740 KB	Output is correct
22	Correct	150 ms	80860 KB	Output is correct
23	Correct	188 ms	80460 KB	Output is correct
24	Correct	164 ms	80332 KB	Output is correct

Subtask #8

0 / 79.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	47444 KB	Output is correct
2	Correct	24 ms	47456 KB	Output is correct
3	Correct	26 ms	47444 KB	Output is correct
4	Correct	26 ms	47392 KB	Output is correct
5	Correct	29 ms	47516 KB	Output is correct
6	Correct	25 ms	47436 KB	Output is correct
7	Correct	25 ms	47524 KB	Output is correct
8	Correct	27 ms	47684 KB	Output is correct
9	Correct	29 ms	47600 KB	Output is correct
10	Correct	28 ms	47600 KB	Output is correct
11	Correct	26 ms	47700 KB	Output is correct
12	Correct	26 ms	47512 KB	Output is correct
13	Correct	25 ms	47452 KB	Output is correct
14	Incorrect	29 ms	47952 KB	Output isn't correct
15	Halted	0 ms	0 KB	-