QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37937#2559. Endless RoadslongleWA 2ms3704kbC++7.6kb2022-07-03 14:27:552022-07-03 14:27:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-03 14:27:56]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：3704kb
查看
  • [2022-07-03 14:27:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;
const int mod = 1e9 + 9;

int n;
vector<pair<int, int>> x;
vector<int> ans;

void solve_case_1() {
    vector<int> vis(101, 0), used(101, 0);
    for (int i = 0; i < n; i++) {
        int p = -1, mn_len = 0;
        for (int j = 0; j < n; j++) {
            if (used[j]) {
                continue;
            }
            int cnt = 0;
            for (int k = x[j].first; k < x[j].second; k++) {
                if (vis[k] == 0) {
                    cnt++;
                }
            }
            if (p == -1 || cnt < mn_len) {
                p = j;
                mn_len = cnt;
            }
        }
        ans.push_back(p + 1);
        used[p] = 1;
        for (int k = x[p].first; k < x[p].second; k++) {
            vis[k] = 1;
        }
    }
}

vector<int> y;
class SegmentTree {
  public:
    SegmentTree(int n) : x((n + 1) << 2, 0), tag((n + 1) << 2, 0) {}
    void pushdown(int u, int l, int r) {
        x[u] = y[r + 1] - y[l];
        tag[u] = 0;
        if (l != r) {
            tag[u << 1] = tag[u << 1 | 1] = 1;
        }
    }

    int query(int u, int l, int r, int ql, int qr) {
        if (tag[u]) {
            pushdown(u, l, r);
        }
        if (l == ql && r == qr) {
            return x[u];
        }
        int mid = (l + r) >> 1;
        if (qr <= mid) {
            return query(u << 1, l, mid, ql, qr);
        } else if (ql > mid) {
            return query(u << 1 | 1, mid + 1, r, ql, qr);
        } else {
            return query(u << 1, l, mid, ql, mid) + query(u << 1 | 1, mid + 1, r, mid + 1, qr);
        }
    }

    void update(int u, int l, int r, int ql, int qr) {
        if (tag[u]) {
            pushdown(u, l, r);
        }
        if (l == ql && r == qr) {
            tag[u] = 1;
            pushdown(u, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        if (qr <= mid) {
            update(u << 1, l, mid, ql, qr);
        } else if (ql > mid) {
            update(u << 1 | 1, mid + 1, r, ql, qr);
        } else {
            update(u << 1, l, mid, ql, mid);
            update(u << 1 | 1, mid + 1, r, mid + 1, qr);
        }
        x[u] = x[u << 1] + x[u << 1 | 1];
    }

    vector<int> x, tag;
};

void solve_case_2() {
    for (int i = 0; i < n; i++) {
        y.push_back(x[i].first);
        y.push_back(x[i].second);
    }
    sort(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    int m = y.size();
    unordered_map<int, int> mp;
    for (int i = 0; i < y.size(); i++) {
        mp[y[i]] = i;
    }
    vector<int> used(m + 1, 0), lens(n + 1, 0);
    for (int i = 0; i < n; i++) {
        lens[i] = x[i].second - x[i].first;
    }
    for (int i = 0; i < n; i++) {
        int p = 0;
        for (int j = 1; j < n; j++) {
            if (lens[j] < lens[p]) {
                p = j;
            }
        }
        lens[p] = 2e9;
        ans.push_back(p + 1);
        for (int j = mp[x[i].first]; j < mp[x[i].second]; j++) {
            if (used[j]) {
                continue;
            }
            used[j] = 1;
            int len = y[j + 1] - y[j];
            for (int k = 0; k < n; k++) {
                if (x[k].first <= y[j]) {//  && y[j + 1] <= x[k].second) {
                    lens[k] -= len;
                }
            }
        }
    }
    /*
    int m = y.size() - 1;
    SegmentTree seg(m);
    vector<int> used(n + 1, 0);
    for (int i = 0; i < n; i++) {
        int p = -1, mn_len = 0;
        for (int j = 0; j < n; j++) {
            if (used[j] == 1) {
                continue;
            }
            int ql = mp[x[j].first], qr = mp[x[j].second] - 1;
            int len = x[j].second - x[j].first - seg.query(1, 0, m - 1, ql, qr);
            // cout << i << ", " << j << ": " << len << endl;
            if (p == -1 || len < mn_len) {
                p = j;
                mn_len = len;
            }
        }
        int ql = mp[x[p].first], qr = mp[x[p].second] - 1;
        seg.update(1, 0, m - 1, ql, qr);
        ans.push_back(p + 1);
        used[p] = 1;
    }
    */
}

vector<tuple<int, int, int>> z;
vector<int> fa, du;

void build_case_4(int l, int r, int fa_id) {
    if (l > r) {
        return;
    }
    if (l == r) {
        fa[get<2>(z[l])] = fa_id;
        return;
    }
    // cout << l << ", " << r << endl;
    if (l == 14375 && r == 69695) {
        int xxxx = 1;
    }
    int lim = l;
    vector<int> pos;
    while (true) {
        int ql = lim, qr = r;
        int ans_pos = ql;
        while (ql <= qr) {
            int mid = (ql + qr) >> 1;
            if (get<1>(z[mid]) <= get<1>(z[lim])) {
                ans_pos = mid;
                ql = mid + 1;
            } else {
                qr = mid - 1;
            }
        }
        lim = ans_pos + 1;
        pos.push_back(ans_pos);
        if (ans_pos == r) {
            break;
        }
    }
    int ql = l;
    for (int i = 0; i < pos.size(); i++) {
        fa[get<2>(z[ql])] = fa_id;
        build_case_4(ql + 1, pos[i], get<2>(z[ql]));
        ql = pos[i] + 1;
    }
}

void solve_case_4() {
    for (int i = 0; i < n; i++) {
        auto [a, b] = x[i];
        z.push_back(make_tuple(a, b, i));
    }
    fa.assign(n + 1, 0);
    du.assign(n + 1, 0);
    // z.push_back(make_tuple(-1, int(1e9 + 1), -1));
    // cout << "YES" << endl;
    sort(z.begin(), z.end(), [](tuple<int, int, int> a, tuple<int, int, int> b) {
        return get<0>(a) < get<0>(b) || (get<0>(a) == get<0>(b) && get<1>(a) >= get<1>(b));
    });
    build_case_4(0, n - 1, -1);
    for (int i = 0; i < n; i++) {
        if (fa[i] != -1) {
            du[fa[i]]++;
        }
    }
    queue<int> q;
    set<pair<int, int>> s;
    vector<int> val(n + 1, 0);
    for (int i = 0; i < n; i++) {
        if (du[i] == 0) {
            q.push(i);
            s.insert(make_pair(x[i].second - x[i].first, i));
        }
        val[i] = x[i].second - x[i].first;
    }
    for (int i = 0; i < n; i++) {
        auto [cnt, idx] = *s.begin();
        ans.push_back(idx + 1);
        s.erase(s.begin());
        if (fa[idx] != -1) {
            val[fa[idx]] -= (x[idx].second - x[idx].first);
            du[fa[idx]]--;
            if (du[fa[idx]] == 0) {
                s.insert(make_pair(val[fa[idx]], fa[idx]));
            }
        }
    }
}

void solve_case_3_4() {

    solve_case_4();
    return;
    /*
    int tag = 1;
    int mxr = -1;
    for (int i = 0; i < n; i++) {
        if (z[i].first >= mxr) {
            mxr = z[i].second;
        } else {
            if (z[i].second <= z[i - 1].second) {

            } else {
                tag = 0;
            }
        }
    }
    if (tag) {
    }
    */
}

void solve(int cas) {
    cin >> n;
    x.clear();
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        x.push_back(make_pair(a, b));
    }
    if (n <= 100) {
        // solve_case_1();
        solve_case_2();
        // solve_case_3_4();
    } else {
        if (n <= 10000) {
            solve_case_2();
        } else {
            solve_case_3_4();
        }
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main() {
    // freopen("ex_color5.in", "r", stdin);
    auto a = clock();
    ios::sync_with_stdio(false);
    int T, cas = 0;
    // cin >> T;
    T = 1;
    while (T--) {
        solve(++cas);
    }
    auto b = clock();
    // cout << (b - a) / CLOCKS_PER_SEC << endl;

    return 0;
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3500kb

input:

6
1 2
2 3
3 4
4 5
1 3
3 5

output:

1 2 5 3 4 6

result:

ok 6 tokens

Test #2:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

4
3 7
10 14
1 6
6 11

output:

1 3 2 4

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

100
50 51
49 51
49 52
48 52
48 53
47 53
47 54
46 54
46 55
45 55
45 56
44 56
44 57
43 57
43 58
42 58
42 59
41 59
41 60
40 60
40 61
39 61
39 62
38 62
38 63
37 63
37 64
36 64
36 65
35 65
35 66
34 66
34 67
33 67
33 68
32 68
32 69
31 69
31 70
30 70
30 71
29 71
29 72
28 72
28 73
27 73
27 74
26 74
26 75
25...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok 100 tokens

Test #4:

score: -100
Wrong Answer
time: 2ms
memory: 3704kb

input:

100
41 42
99 100
47 48
50 51
56 57
61 62
27 28
85 86
44 45
3 4
26 27
20 21
92 93
33 34
86 87
69 70
84 85
62 63
81 82
2 3
13 14
32 33
82 83
70 71
46 47
45 46
19 20
83 84
57 59
63 65
59 61
82 84
45 47
48 50
70 72
42 44
84 86
26 28
61 63
2 4
17 19
65 67
54 56
67 69
96 99
42 45
47 50
34 37
14 17
51 54
7...

output:

1 7 10 11 12 14 20 21 27 22 40 38 41 49 53 56 64 70 9 68 75 80 59 3 25 26 36 87 88 48 62 67 81 33 46 61 72 86 82 34 47 94 71 4 43 93 5 50 54 60 90 79 29 97 31 57 6 18 39 73 91 96 30 42 58 44 16 52 99 77 24 35 51 66 89 19 76 78 23 28 32 85 95 17 8 37 15 69 74 84 13 55 65 45 2 63 83 92 98 100

result:

wrong answer 2nd words differ - expected: '2', found: '7'
English 繁體中文 简体中文

Server Time: 2025-01-20 21:16:34 | OpenSource Project