oj.uz

답안 #652746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652746 2022-10-24T06:42:10 Z XCAC197 함박 스테이크 (JOI20_hamburg) C++14
15 / 100
 225 ms 81168 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -