oj.uz

답안 #80230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80230 2018-10-19T15:32:34 Z Nazik_number_one 자리 배치 (IOI18_seats) C++14
70 / 100
 4000 ms 131912 KB 
#include "seats.h"

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node{
    int s, k, ob;
    node(){
        s = 1e9;
        k = ob = 0;
    }
    node (node a, node b){
        s = min(a.s, b.s);
        k = ob = 0;
        if (a.s == s)k += a.k;
        if (b.s == s)k += b.k;
    }
};
vector < vector < int > > aa;
int n, m, t, sz;
pair < int, int > p[N];
node tree[N * 4];

inline node mrg(node a, node b){
    node c;
    c.s = min(a.s, b.s);
    c.k = c.ob = 0;
    if (a.s == c.s)c.k += a.k;
    if (b.s == c.s)c.k += b.k;
    return c;
}

inline void push(int v, int l, int r){
    if (tree[v].ob == 0)return;
    tree[v].s += tree[v].ob;
    if (l != r){
        tree[v + v].ob += tree[v].ob;
        tree[v + v + 1].ob += tree[v].ob;
    }
    tree[v].ob = 0;
}

inline void add(int v, int l, int r, int ll, int rr, int x){
    push(v, l, r);
    if (l > r || ll > rr || l > rr || r < ll)return;
    if (l >= ll && r <= rr){
        tree[v].ob = x;
        push(v, l, r);
        return;
    }
    int mid = (l + r) / 2;
    add(v + v, l, mid, ll, rr, x);
    add(v + v + 1, mid + 1, r, ll, rr, x);
    tree[v] = mrg(tree[v + v], tree[v + v + 1]);
}

inline node get(int v, int l, int r, int ll, int rr){
    push(v, l, r);
    if (l > r || ll > rr || l > rr || r < ll)return node();
    if (l >= ll && r <= rr)return tree[v];
    int mid = (l + r) / 2;
    node x = get(v + v, l, mid, ll, rr), y = get(v + v + 1, mid + 1, r, ll, rr);
    tree[v] = mrg(tree[v + v], tree[v + v + 1]);
    return mrg(x, y);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H, m = W;
    t = n * m;
    sz = 1;
    while (sz < t){
        sz *= 2;
    }
    for (int i = sz; i <= sz + t - 1; ++i){
        tree[i].k = 1;
        tree[i].s = 0;
    }
    for (int i = sz - 1; i > 0; --i){
        tree[i].s = 0;
        tree[i].k = tree[i + i].k + tree[i + i + 1].k;
    }
    aa.resize(n + 2);
    aa[0].resize(m + 2, t);
    for (int i = 1; i <= n; ++i){
        aa[i].resize(m + 2);
        aa[i][0] = t;
        aa[i][m + 1] = t;
    }
    aa[n + 1].resize(m + 2, t);
    for (int i = 0; i < t; ++i){
        aa[R[i] + 1][C[i] + 1] = i;
        p[i + 1] = make_pair(R[i] + 1, C[i] + 1);
    }
    vector < int > b;
    b.resize(4);
    for (int i = 1; i <= n + 1; ++i){
        for (int j = 1; j <= m + 1; ++j){
            b[0] = aa[i - 1][j - 1], b[1] = aa[i][j - 1], b[2] = aa[i - 1][j], b[3] = aa[i][j];
            sort(b.begin(), b.end());
            add(1, sz, sz + sz - 1, sz + b[0], sz + b[1] - 1, 1);
            add(1, sz, sz + sz - 1, sz + b[2], sz + b[3] - 1, 1);
        }
    }
}

int swap_seats(int a, int b) {
    a++;
    b++;
    //cout <<a<<" "<<b<<" "<<" "<<p[a].first<<" "<<p[a].second<<" "<<p[b].first<<" "<<p[b].second<<endl;
    vector < pair < int, int > > c;
    c.push_back(make_pair(p[a].first, p[a].second));
    c.push_back(make_pair(p[a].first + 1, p[a].second));
    c.push_back(make_pair(p[a].first, p[a].second + 1));
    c.push_back(make_pair(p[a].first + 1, p[a].second + 1));
    c.push_back(make_pair(p[b].first, p[b].second));
    c.push_back(make_pair(p[b].first + 1, p[b].second));
    c.push_back(make_pair(p[b].first, p[b].second + 1));
    c.push_back(make_pair(p[b].first + 1, p[b].second + 1));
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    vector < int > bb;
    bb.resize(4);
    for (int e = 0; e < c.size(); ++e){
        int i = c[e].first, j = c[e].second;
        bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
        sort(bb.begin(), bb.end());
        add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, -1);
        add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, -1);
    }
    //return 0;
    swap(aa[p[a].first][p[a].second], aa[p[b].first][p[b].second]);
    swap(p[a], p[b]);
    for (int e = 0; e < c.size(); ++e){
        int i = c[e].first, j = c[e].second;
        bb[0] = aa[i - 1][j - 1], bb[1] = aa[i][j - 1], bb[2] = aa[i - 1][j], bb[3] = aa[i][j];
        sort(bb.begin(), bb.end());
        add(1, sz, sz + sz - 1, sz + bb[0], sz + bb[1] - 1, 1);
        add(1, sz, sz + sz - 1, sz + bb[2], sz + bb[3] - 1, 1);
    }
    node v = get(1, sz, sz + sz - 1, sz, sz + t - 1);
    //cout <<v.s<<" "<<v.k<<endl;
    if (v.s == 4)return v.k;else return 0;
}

Compilation message

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:123:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int e = 0; e < c.size(); ++e){
                     ~~^~~~~~~~~~
seats.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int e = 0; e < c.size(); ++e){
                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 47480 KB Output is correct
2 Correct 69 ms 47596 KB Output is correct
3 Correct 84 ms 47604 KB Output is correct
4 Correct 73 ms 47640 KB Output is correct
5 Correct 65 ms 47704 KB Output is correct
6 Correct 81 ms 47724 KB Output is correct
7 Correct 84 ms 47764 KB Output is correct
8 Correct 77 ms 47848 KB Output is correct
9 Correct 82 ms 47924 KB Output is correct
10 Correct 86 ms 48056 KB Output is correct
11 Correct 81 ms 48056 KB Output is correct
12 Correct 68 ms 48056 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 47480 KB Output is correct
2 Correct 69 ms 47596 KB Output is correct
3 Correct 84 ms 47604 KB Output is correct
4 Correct 73 ms 47640 KB Output is correct
5 Correct 65 ms 47704 KB Output is correct
6 Correct 81 ms 47724 KB Output is correct
7 Correct 84 ms 47764 KB Output is correct
8 Correct 77 ms 47848 KB Output is correct
9 Correct 82 ms 47924 KB Output is correct
10 Correct 86 ms 48056 KB Output is correct
11 Correct 81 ms 48056 KB Output is correct
12 Correct 68 ms 48056 KB Output is correct
13 Correct 130 ms 48552 KB Output is correct
14 Correct 160 ms 48552 KB Output is correct
15 Correct 103 ms 48552 KB Output is correct
16 Correct 91 ms 49008 KB Output is correct
17 Correct 133 ms 49008 KB Output is correct
18 Correct 109 ms 49008 KB Output is correct
19 Correct 109 ms 49008 KB Output is correct
20 Correct 100 ms 49088 KB Output is correct
21 Correct 84 ms 49120 KB Output is correct
22 Correct 87 ms 49772 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2760 ms 79324 KB Output is correct
2 Correct 1346 ms 79324 KB Output is correct
3 Correct 1237 ms 79372 KB Output is correct
4 Correct 1051 ms 79372 KB Output is correct
5 Correct 1237 ms 79372 KB Output is correct
6 Correct 1070 ms 79372 KB Output is correct
7 Correct 1129 ms 80192 KB Output is correct
8 Correct 1148 ms 80852 KB Output is correct
9 Correct 1291 ms 80968 KB Output is correct
10 Correct 1147 ms 80968 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 80968 KB Output is correct
2 Correct 237 ms 80968 KB Output is correct
3 Correct 1150 ms 80968 KB Output is correct
4 Correct 2641 ms 80968 KB Output is correct
5 Correct 962 ms 88672 KB Output is correct
6 Correct 2714 ms 131912 KB Output is correct
7 Correct 1070 ms 131912 KB Output is correct
8 Correct 1347 ms 131912 KB Output is correct
9 Correct 1166 ms 131912 KB Output is correct
10 Correct 1174 ms 131912 KB Output is correct
11 Correct 1112 ms 131912 KB Output is correct

Subtask #5
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 131912 KB Output is correct
2 Correct 180 ms 131912 KB Output is correct
3 Correct 288 ms 131912 KB Output is correct
4 Correct 320 ms 131912 KB Output is correct
5 Correct 517 ms 131912 KB Output is correct
6 Correct 1589 ms 131912 KB Output is correct
7 Correct 1907 ms 131912 KB Output is correct
8 Correct 1508 ms 131912 KB Output is correct
9 Correct 3573 ms 131912 KB Output is correct
10 Correct 1444 ms 131912 KB Output is correct
11 Correct 1474 ms 131912 KB Output is correct
12 Correct 1526 ms 131912 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 47480 KB Output is correct
2 Correct 69 ms 47596 KB Output is correct
3 Correct 84 ms 47604 KB Output is correct
4 Correct 73 ms 47640 KB Output is correct
5 Correct 65 ms 47704 KB Output is correct
6 Correct 81 ms 47724 KB Output is correct
7 Correct 84 ms 47764 KB Output is correct
8 Correct 77 ms 47848 KB Output is correct
9 Correct 82 ms 47924 KB Output is correct
10 Correct 86 ms 48056 KB Output is correct
11 Correct 81 ms 48056 KB Output is correct
12 Correct 68 ms 48056 KB Output is correct
13 Correct 130 ms 48552 KB Output is correct
14 Correct 160 ms 48552 KB Output is correct
15 Correct 103 ms 48552 KB Output is correct
16 Correct 91 ms 49008 KB Output is correct
17 Correct 133 ms 49008 KB Output is correct
18 Correct 109 ms 49008 KB Output is correct
19 Correct 109 ms 49008 KB Output is correct
20 Correct 100 ms 49088 KB Output is correct
21 Correct 84 ms 49120 KB Output is correct
22 Correct 87 ms 49772 KB Output is correct
23 Correct 2760 ms 79324 KB Output is correct
24 Correct 1346 ms 79324 KB Output is correct
25 Correct 1237 ms 79372 KB Output is correct
26 Correct 1051 ms 79372 KB Output is correct
27 Correct 1237 ms 79372 KB Output is correct
28 Correct 1070 ms 79372 KB Output is correct
29 Correct 1129 ms 80192 KB Output is correct
30 Correct 1148 ms 80852 KB Output is correct
31 Correct 1291 ms 80968 KB Output is correct
32 Correct 1147 ms 80968 KB Output is correct
33 Correct 132 ms 80968 KB Output is correct
34 Correct 237 ms 80968 KB Output is correct
35 Correct 1150 ms 80968 KB Output is correct
36 Correct 2641 ms 80968 KB Output is correct
37 Correct 962 ms 88672 KB Output is correct
38 Correct 2714 ms 131912 KB Output is correct
39 Correct 1070 ms 131912 KB Output is correct
40 Correct 1347 ms 131912 KB Output is correct
41 Correct 1166 ms 131912 KB Output is correct
42 Correct 1174 ms 131912 KB Output is correct
43 Correct 1112 ms 131912 KB Output is correct
44 Correct 113 ms 131912 KB Output is correct
45 Correct 180 ms 131912 KB Output is correct
46 Correct 288 ms 131912 KB Output is correct
47 Correct 320 ms 131912 KB Output is correct
48 Correct 517 ms 131912 KB Output is correct
49 Correct 1589 ms 131912 KB Output is correct
50 Correct 1907 ms 131912 KB Output is correct
51 Correct 1508 ms 131912 KB Output is correct
52 Correct 3573 ms 131912 KB Output is correct
53 Correct 1444 ms 131912 KB Output is correct
54 Correct 1474 ms 131912 KB Output is correct
55 Correct 1526 ms 131912 KB Output is correct
56 Correct 214 ms 131912 KB Output is correct
57 Correct 491 ms 131912 KB Output is correct
58 Correct 763 ms 131912 KB Output is correct
59 Correct 2245 ms 131912 KB Output is correct
60 Execution timed out 4099 ms 131912 KB Time limit exceeded
61 Halted 0 ms 0 KB -