QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#136258#2412. Canvas LineNightW0lf#WA 6ms22616kbC++235.5kb2023-08-07 18:05:492023-08-07 18:05:51

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 18:05:51]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:22616kb
  • [2023-08-07 18:05:49]
  • 提交

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)