Submission #1048917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048917		kostia244	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1435 ms	264420 KiB

hamburg

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;

const int inf = 1<<30;
struct Rect {
    array<array<int, 2>, 2> ranges;
    void rotate(int c) {
        while(c--) {
            for(int i = 0; i < 2; i++) {
                ranges[0][i] = -exchange(ranges[1][i], ranges[0][i]);
            }
            for(int i = 0; i < 2; i++) {
                if(ranges[i][0] > ranges[i][1])
                    swap(ranges[i][0], ranges[i][1]);
            }
        }
    }
    friend Rect intersect(const Rect &a, const Rect &b) {
        Rect res;
        for(int i = 0; i < 2; i++) {
            res.ranges[i][0] = max(a.ranges[i][0], b.ranges[i][0]);
            res.ranges[i][1] = min(a.ranges[i][1], b.ranges[i][1]);
        }
        return res;
    }
    bool contains(array<int, 2> P) {
        for(int i = 0; i < 2; i++) {
            if(P[i] < ranges[i][0] || P[i] > ranges[i][1])
                return false;
        }
        return true;
    }
    bool empty() {
        for(int i = 0; i < 2; i++) 
            if(ranges[i][0] > ranges[i][1])
                return true;
        return false;
    }
};

Rect intersectAll(vector<Rect> &v) {
    Rect res;
    res.ranges[0][0] = res.ranges[1][0] = -inf;
    res.ranges[0][1] = res.ranges[1][1] = inf;
    for(auto &i : v)
        res = intersect(res, i);
    return res;
}

vector<Rect> prune(vector<Rect> v, array<int, 2> P) {
    vector<Rect> res;
    for(auto i : v) if(!i.contains(P)) {
        res.push_back(i);
    }
    return res;
}

array<vector<int>, 2> compress(vector<Rect> &v) {
    array<vector<int>, 2> clist;
    for(auto r : v) {
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                clist[i].push_back(r.ranges[i][j]);
            }
        }
    }
    for(auto &c : clist) sort(all(c)), c.erase(unique(all(c)), c.end());
    for(auto &r : v) {
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                r.ranges[i][j] = lower_bound(all(clist[i]), r.ranges[i][j]) - clist[i].begin();
            }
        }
    }
    return clist;
}

// Solve k<=3 and k=4 if we use a corner or intersection is non-empty
vector<array<int, 2>> solve_corner(vector<Rect> rects, int k) {
    if(k < 1) return {};
    
    //All intersect use 1, not tested
    Rect I = intersectAll(rects);
    if(I.ranges[0][0] <= I.ranges[0][1] && I.ranges[1][0] <= I.ranges[1][1]) {
        return {{I.ranges[0][0], I.ranges[1][0]}};
    }
    
    // for(auto &c : I.ranges) {
    //     for(auto &v : c) cout << v << ", ";
    //     cout << endl;
    // }
    //1D case; not tested
    int rot = 0;
    if(I.ranges[1][0] <= I.ranges[1][1]) {
        rot++;
        I.rotate(1);
        for(auto &i : rects) i.rotate(1);
    }
    if(I.ranges[0][0] <= I.ranges[0][1]) {
        vector<array<int, 2>> segs;//{R, L}
        for(auto r : rects) {
            segs.push_back({r.ranges[1][1], r.ranges[1][0]});
        }
        sort(all(segs));
        int covered = -1;
        vector<array<int, 2>> sol;
        for(auto [r, l] : segs) {
            if(l <= covered) {
                assert(covered <= r);
            } else {
                sol.push_back({I.ranges[0][0], covered = r});
            }
        }
        if(sol.size() > k) return {};
        if(rot) {
            for(auto &[x, y] : sol) {
                y = -exchange(x, y);
            }
        }
        return sol;
    }
    
    assert(!rot);
    
    //Use corner case; not tested
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            array<int, 2> P = {I.ranges[0][i], I.ranges[1][j]};
            auto tmp = solve_corner(prune(rects, P), k - 1);
            if(!tmp.empty()) {
                tmp.push_back(P);
                return tmp;
            }
        }
    }
    
    return {};
}

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct TwoSat {
	int N;
	vector<vi> gr;
	vi values; // 0 = false, 1 = true

	TwoSat(int n = 0) : N(n), gr(2*n) {}

	int addVar() { // (optional)
		gr.emplace_back();
		gr.emplace_back();
		return N++;
	}

	void either(int f, int j) {
		f = max(2*f, -1-2*f);
		j = max(2*j, -1-2*j);
		gr[f].push_back(j^1);
		gr[j].push_back(f^1);
	}
	void setValue(int x) { either(x, x); }

	void atMostOne(const vi& li) { // (optional)
		if (sz(li) <= 1) return;
		int cur = ~li[0];
		rep(i,2,sz(li)) {
			int next = addVar();
			either(cur, ~li[i]);
			either(cur, next);
			either(~li[i], next);
			cur = ~next;
		}
		either(cur, ~li[1]);
	}

	vi val, comp, z; int time = 0;
	int dfs(int i) {
		int low = val[i] = ++time, x; z.push_back(i);
		for(int e : gr[i]) if (!comp[e])
			low = min(low, val[e] ?: dfs(e));
		if (low == val[i]) do {
			x = z.back(); z.pop_back();
			comp[x] = low;
			if (values[x>>1] == -1)
				values[x>>1] = x&1;
		} while (x != i);
		return val[i] = low;
	}

	bool solve() {
		values.assign(N, -1);
		val.assign(2*N, 0); comp = val;
		rep(i,0,2*N) if (!comp[i]) dfs(i);
		rep(i,0,N) if (comp[2*i] == comp[2*i+1]) return 0;
		return 1;
	}
};

//solve k=4, no point in the corner -> all on the perimeter
vector<array<int, 2>> solve_perim(vector<Rect> rects) {
    auto clist = compress(rects);
    
    Rect I = intersectAll(rects);
    swap(I.ranges[0][0], I.ranges[0][1]);
    swap(I.ranges[1][0], I.ranges[1][1]);
    for(int i = 0; i < 2; i++) assert(I.ranges[i][0] < I.ranges[i][1]);//because we already used the other function
    
    // cout << I.ranges[0][0] << " " << I.ranges[0][1] << endl;
    // cout << I.ranges[1][0] << " " << I.ranges[1][1] << endl;
    
    vector<vector<int>> myVars(rects.size());
    vector<int> starts;
    TwoSat sat;
    for(int c = 0; c < 2; c++) {
        for(int x = 0; x < 2; x++) {
            
            Rect l = I;
            l.ranges[c][x] = l.ranges[c][x^1];
            l.ranges[c^1][0]++;
            l.ranges[c^1][1]--;
            
            int len = l.ranges[c^1][1] - l.ranges[c^1][0] + 1;
                // cout << l.ranges[c][x] << " : " << l.ranges[c^1][0] << " " << l.ranges[c^1][1] << endl;
            
            int start = sat.addVar();
            starts.push_back(start);
            sat.setValue(~start);
            for(int i = 1; i <= len; i++) {
                assert(sat.addVar() == start + i);   
                sat.either(~(start + i - 1), (start + i));
            }
            int lid = 2*c+x;
            for(int i = 0; i < rects.size(); i++) {
                auto inter = intersect(l, rects[i]);
                // cout << "I" << inter.ranges[c][x] << " : " << inter.ranges[c^1][0] << " " << inter.ranges[c^1][1] << endl;
                if(inter.empty()) continue;
                int b = inter.ranges[c^1][0] - l.ranges[c^1][0] + 1;
                int e = inter.ranges[c^1][1] - l.ranges[c^1][0] + 1;
                int x = sat.addVar();
                myVars[i].push_back(x);
                sat.either(~x, ~(start + b - 1));
                sat.either(~x, start + e);
                // cout << "Line " << lid << "; Rect " << i << "_" << x << " : not " << start + b - 1 << " or " << start + e << endl;
            }
        }
    }
    
    for(auto v : myVars) {
        if(v.size() == 1) sat.setValue(v[0]);//, cout << "SET " << v[0] << endl;
        if(v.size() == 2) sat.either(v[0], v[1]);//, cout << "OR " << v[0] << " " << v[1] << endl;
    }
    
    assert(sat.solve());
    
    vector<array<int, 2>> ans;
    for(int c = 0; c < 2; c++) {
        for(int x = 0; x < 2; x++) {
            
            Rect l = I;
            l.ranges[c][x] = l.ranges[c][x^1];
            l.ranges[c^1][0]++;
            l.ranges[c^1][1]--;
            int len = l.ranges[c^1][1] - l.ranges[c^1][0] + 1;
            
            int start = starts[c*2+x];
            
            // for(int i = 0; i <= len; i++) {
            //     cout << sat.values[start+i] << " ";
            // }cout << endl;
            
            array<int, 2> pt;
            pt[c] = l.ranges[c][x];
            pt[c^1] = l.ranges[c^1][0] - 1;
            while(!sat.values[start]) {
                start++;
                pt[c^1]++;
            }
            ans.push_back(pt);
        }
    }
    
    for(auto &i : ans) {
        for(int c = 0; c < 2; c++) {
            i[c] = clist[c][i[c]];
        }
    }
    
    return ans;
}

vector<array<int, 2>> solve() {
    int n, k;
    cin >> n >> k;
    vector<Rect> rects(n);
    for(auto &r : rects) {
        // cin >> r.ranges[0][0] >> r[1][0] >> r[0][1] >> r[1][1];
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                cin >> r.ranges[j][i];
        
    }
    
    auto res = solve_corner(rects, k);
    if(res.empty() && k == 4) {
        res = solve_perim(rects);
    }
    assert(!res.empty());
    while(res.size() < k) res.push_back(res.back());

    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    auto out = solve();
    for(auto [x, y] : out) {
        cout << x << " " << y << '\n';
    }
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve_corner(std::vector<Rect>, int)':
hamburg.cpp:116:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  116 |         if(sol.size() > k) return {};
      |            ~~~~~~~~~~~^~~
hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve_perim(std::vector<Rect>)':
hamburg.cpp:239:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |             for(int i = 0; i < rects.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
hamburg.cpp:238:17: warning: unused variable 'lid' [-Wunused-variable]
  238 |             int lid = 2*c+x;
      |                 ^~~
hamburg.cpp:269:17: warning: unused variable 'len' [-Wunused-variable]
  269 |             int len = l.ranges[c^1][1] - l.ranges[c^1][0] + 1;
      |                 ^~~
hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve()':
hamburg.cpp:314:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  314 |     while(res.size() < k) res.push_back(res.back());
      |           ~~~~~~~~~~~^~~

• 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