oj.uz

Submission #1048906

# Submission time Handle Problem Language Result Execution time Memory
1048906 2024-08-08T10:50:08 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 164 ms 30068 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
    
    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:236:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Rect>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |             for(int i = 0; i < rects.size(); i++) {
      |                            ~~^~~~~~~~~~~~~~
hamburg.cpp:235:17: warning: unused variable 'lid' [-Wunused-variable]
  235 |             int lid = 2*c+x;
      |                 ^~~
hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve()':
hamburg.cpp:303: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]
  303 |     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 1 ms 348 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 616 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 344 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 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 600 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 484 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 7 ms 2304 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 1 ms 348 KB Output is correct
5 Correct 46 ms 6484 KB Output is correct
6 Correct 72 ms 6648 KB Output is correct
7 Correct 60 ms 6484 KB Output is correct
8 Correct 52 ms 6484 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 616 KB Output is correct
5 Correct 47 ms 11908 KB Output is correct
6 Correct 56 ms 16332 KB Output is correct
7 Correct 48 ms 11980 KB Output is correct
8 Correct 63 ms 22396 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 344 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 2 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 65 ms 8832 KB Output is correct
14 Correct 72 ms 8696 KB Output is correct
15 Correct 68 ms 8828 KB Output is correct
16 Correct 58 ms 8660 KB Output is correct
17 Correct 70 ms 8836 KB Output is correct
18 Correct 65 ms 8832 KB Output is correct
19 Correct 49 ms 15732 KB Output is correct
20 Correct 164 ms 30068 KB Output is correct
21 Correct 51 ms 17352 KB Output is correct
22 Correct 81 ms 28392 KB Output is correct
23 Correct 117 ms 28492 KB Output is correct
24 Correct 108 ms 28924 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 484 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 7 ms 2304 KB Output isn't correct
15 Halted 0 ms 0 KB -