Submission #652748

#	Time	Username	Problem	Language	Result	Execution time	Memory
652748		XCAC197	Hamburg Steak (JOI20_hamburg)	C++14	100 / 100	2539 ms	186296 KiB

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(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) <= uu && dd <= (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) <= uu && dd <= (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) <= rr && ll <= (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) <= rr && ll <= (maxL+1)){
                        inter.push_back(make_pair(4, make_pair(max(minR+1, ll), min(maxL-1, rr))));
                    }
                }
                if(inter.size() >= 3){
                    //do nothing
                }else if(inter.size() == 0){
                 //   cout << "Nothing" << (dd <= minU && minU <= uu) << endl;
                    //do nothing
                }else if(inter.size() == 1){
                   // cout << "IS SINGLE" << endl;
                    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;
                    }
                  //  cout << "IS DOUBLE" << endl;
                    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)){
      //  cout << "***" << endl;
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i].x << " " << ans[i].y << endl;
        }
    }else{
        cout << "I GIVE UP GOODBYE" << endl;
    }
    
      //  vector <rect> rekt = rectArr;
      //  for(int i = 0; i < ans.size(); i++){
     //       rekt = removeSkewered(rekt, ans[i]);
       // }
       // cout << rekt.size() << endl;
      //  for(int i = 0; i < rekt.size(); i++){
           // cout << rekt[i].l << " " << rekt[i].r << " " << rekt[i].d << " " << rekt[i].u << endl;
      //  }
      //  cout << endl;
}

Compilation message (stderr)

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: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:376:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  376 |         for(int i = 0; i < ans.size(); i++){
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79