QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#136258 | #2412. Canvas Line | NightW0lf# | WA | 6ms | 22616kb | C++23 | 5.5kb | 2023-08-07 18:05:49 | 2023-08-07 18:05:51 |
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(edges[pos1].first > pts[pos2].first) return recurse(pos1 + 1, pos2, 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) {
//cout << pos1 << " " << pts[pos2].first << " " << total << "\n";
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 ;
}
if(edges[pos1].first > pts[pos2].first) print(pos1 + 1, pos2, 0);
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( total<2 and 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});
is_point[x.first] = 1;
}
if(is_point.find(x.second) == is_point.end()) {
pts.push_back({x.second, 0});
is_point[x.second] = 1;
}
if(is_point.find(x.second - 1) == is_point.end()) {
pts.push_back({x.second - 1, 0});
is_point[x.second - 1] = 1;
}
if(is_point.find(x.first + 1) == is_point.end()) {
pts.push_back({x.first + 1, 0});
is_point[x.first + 1] = 1;
}
}
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: 100
Accepted
time: 0ms
memory: 3504kb
input:
5 0 100 100 200 200 300 300 400 400 500 2 100 200
output:
4 0 300 400 401
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
20 0 100 100 200 200 300 300 400 400 500 500 600 600 700 700 800 800 900 900 1000 1000 1100 1100 1200 1200 1300 1300 1400 1400 1500 1500 1600 1600 1700 1700 1800 1800 1900 1900 2000 3 300 900 2000
output:
18 0 100 200 400 500 600 700 800 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900
result:
ok
Test #3:
score: 0
Accepted
time: 6ms
memory: 22616kb
input:
300 0 10 10 20 20 30 30 40 40 50 50 60 60 70 70 80 80 90 90 100 100 110 110 120 120 130 130 140 140 150 150 160 160 170 170 180 180 190 190 200 200 210 210 220 220 230 230 240 240 250 250 260 260 270 270 280 280 290 290 300 300 310 310 320 320 330 330 340 340 350 350 360 360 370 370 380 380 390 390 ...
output:
299 0 20 21 50 60 70 71 90 100 101 120 130 131 151 160 170 180 190 191 210 220 221 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650 660 670 680 690 700 710 720 730 740 750 760 770 7...
result:
ok
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3540kb
input:
1 9000 9020 2 8990 9030
output:
0 9000
result:
wrong answer Team output wrong number of pegs 0 (output 1 numbers)