QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136222#2412. Canvas LineNightW0lf#WA 0ms3476kbC++235.1kb2023-08-07 17:08:452023-08-07 17:08:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-07 17:08:49]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3476kb
  • [2023-08-07 17:08:45]
  • 提交

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";
    }
}

詳細信息

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