oj.uz

Submission #1048911

# Submission time Handle Problem Language Result Execution time Memory
1048911 2024-08-08T10:59:09 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 164 ms 30372 KB 
#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]);
                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 start = starts[c*2+x];
            array<int, 2> pt;
            pt[c] = l.ranges[c][x];
            pt[c^1] = l.ranges[c^1][0] - 1;
            while(!sat.val[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

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: In function 'std::vector<std::array<int, 2> > solve()':
hamburg.cpp:306: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]
  306 |     while(res.size() < k) res.push_back(res.back());
      |           ~~~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Incorrect 6 ms 2060 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 43 ms 6664 KB Output is correct
6 Correct 43 ms 6480 KB Output is correct
7 Correct 42 ms 6480 KB Output is correct
8 Correct 43 ms 6480 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 46 ms 11984 KB Output is correct
6 Correct 59 ms 16332 KB Output is correct
7 Correct 47 ms 11980 KB Output is correct
8 Correct 64 ms 22648 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 59 ms 8820 KB Output is correct
14 Correct 61 ms 8832 KB Output is correct
15 Correct 60 ms 8656 KB Output is correct
16 Correct 66 ms 8652 KB Output is correct
17 Correct 58 ms 8920 KB Output is correct
18 Correct 58 ms 8656 KB Output is correct
19 Correct 47 ms 14532 KB Output is correct
20 Correct 164 ms 30372 KB Output is correct
21 Correct 57 ms 18044 KB Output is correct
22 Correct 83 ms 28160 KB Output is correct
23 Correct 129 ms 29184 KB Output is correct
24 Correct 95 ms 28716 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 720 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 720 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Incorrect 6 ms 2060 KB Output isn't correct
15 Halted 0 ms 0 KB -