QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136222 | #2412. Canvas Line | NightW0lf# | WA | 0ms | 3476kb | C++23 | 5.1kb | 2023-08-07 17:08:45 | 2023-08-07 17:08:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> pts;
vector<pair<int, int>> edges;
map<int, bool> is_point;
vector<vector<vector<int>>> dp;
int recurse(int pos1, int pos2, int total) {
//cout << pos1 << " " << pos2 << " " << total << "\n";
if(total > 2) {
//cout << "!";
return INT_MAX;
}
int npos1 = pos1;
int flag = 0;
while(npos1 < edges.size() and edges[npos1].second < pts[pos2].first) {
npos1++;
flag = 1;
}
if(flag == 1) total = 0;
if(npos1 == edges.size()) {
return 0;
}
// if(pos2 == pts.size()) {
// return INT_MAX;
// }
if(dp[npos1][pos2][total] != -1) return dp[npos1][pos2][total];
int ans = INT_MAX;
if(pts[pos2].second == 1) {
if(edges[npos1].second == pts[pos2].first) {
int nxt = 0;
if(npos1 + 1 < edges.size() and edges[npos1 + 1].first == pts[pos2].first) nxt++;
if(total + 1 == 2) return recurse(npos1 + 1, pos2 + 1, nxt);
else return INT_MAX;
}
else {
return recurse(npos1, pos2 + 1, total + 1);
}
}
else {
if(edges[npos1].second == pts[pos2].first) {
ans = INT_MAX;
int nxt = 0;
if(npos1 + 1 < edges.size() and edges[npos1 + 1].first == pts[pos2].first) nxt++;
if(total == 2) ans = min(ans, recurse(npos1 + 1, pos2 + 1, 0));
if(total == 1) ans = min(ans, recurse(npos1 + 1, pos2 + 1, nxt) + 1);
}
else {
ans = min(recurse(npos1, pos2 + 1, total + 1) + 1, recurse(npos1, pos2 + 1, total));
}
}
return dp[npos1][pos2][total] = ans;
}
vector<int> res;
void print(int pos1, int pos2, int total) {
int npos1 = pos1;
int flag = 0;
while(npos1 < edges.size() and edges[npos1].second < pts[pos2].first) {
npos1++;
flag = 1;
}
if(flag == 1) total = 0;
if(npos1 == edges.size()) {
return ;
}
int curr_ans = recurse(npos1, pos2, total);
if(pts[pos2].second == 1) {
if(edges[npos1].second == pts[pos2].first) {
int nxt = 0;
if(npos1 + 1 < edges.size() and edges[npos1 + 1].first == pts[pos2].first) nxt++;
if(total + 1 == 2) {
print(npos1 + 1, pos2 + 1, nxt);
return ;
}
}
else {
print(npos1, pos2 + 1, total + 1);
return ;
}
}
else {
if(edges[npos1].second == pts[pos2].first) {
int nxt = 0;
if(npos1 + 1 < edges.size() and edges[npos1 + 1].first == pts[pos2].first) nxt++;
if(total == 2 and curr_ans == recurse(npos1 + 1, pos2 + 1, 0)){
print(npos1 + 1, pos2 + 1, 0);
return ;
} //ans = min(ans, recurse(npos1 + 1, pos2 + 1, 0));
//if(total == 1) ans = min(ans, recurse(npos1 + 1, pos2 + 1, nxt) + 1);
else if(total == 1 and curr_ans == recurse(npos1 + 1, pos2 + 1, nxt) + 1) {
res.push_back(pts[pos2].first);
print(npos1 + 1, pos2 + 1, nxt);
return ;
}
}
else {
if(recurse(npos1, pos2 + 1, total + 1) + 1 == curr_ans) {
res.push_back(pts[pos2].first);
print(npos1, pos2 + 1, total + 1);
}
else {
print(npos1, pos2 + 1, total);
}
//ans = min(recurse(npos1, pos2 + 1, total + 1) + 1, recurse(npos1, pos2 + 1, total));
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n; cin >> n;
for(int i = 1; i <= n; i++) {
int l, r; cin >> l >> r;
edges.push_back({l, r});
}
sort(edges.begin(), edges.end());
int p; cin >> p;
for(int i = 1; i <= p; i++) {
int x; cin >> x;
pts.push_back({x, 1});
is_point[x] = 1;
}
for(auto x: edges) {
if(is_point.find(x.first) == is_point.end()) {
pts.push_back({x.first, 0});
}
if(is_point.find(x.second) == is_point.end()) {
pts.push_back({x.second, 0});
}
if(is_point.find(x.second - 1) == is_point.end()) {
pts.push_back({x.second - 1, 0});
}
if(is_point.find(x.first + 1) == is_point.end()) {
pts.push_back({x.first + 1, 0});
}
}
sort(pts.begin(), pts.end());
///for(auto x: pts) cout << x.first << " " << x.second << "\n";
dp.assign(n + 1, vector<vector<int>>(pts.size() + 1, vector<int>(4, -1)));
int ans = recurse(0, 0, 0);
if(ans >= INT_MAX) cout << "impossible\n";
else {
print(0, 0, 0);
cout << ans << "\n";
for(auto x: res) cout << x << " ";
cout << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3476kb
input:
5 0 100 100 200 200 300 300 400 400 500 2 100 200
output:
4 0 300 400 400
result:
wrong answer Team has multiple pegs at x=400