QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#375658#4088. 총 쏘기hotboy27030 761ms6772kbC++142.2kb2024-04-03 14:36:052024-04-03 14:36:05

Judging History

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

  • [2024-04-03 14:36:05]
  • 评测
  • 测评结果：0
  • 用时：761ms
  • 内存：6772kb
查看
  • [2024-04-03 14:36:05]
  • 提交

answer

//#include "gun.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
namespace{
    const ll MAXN = 1e5;
    ll n;
    ll a[MAXN+100];
    ll b[MAXN+100];
    ll rev[MAXN+100];
    vector <pair <int,int> > ans;
    void solve(){
        set <ll> s;
        for (ll i = 1;i <= n;i ++)s.insert(i);
        for (ll i = 1;i <= n;i ++){b[i] = n + 1 - a[i];rev[b[i]] = i;}
        vector <ll> lds;
        while (sz(s)){
            set <ll> pre_s = s;
            vector <ll> sus;
            lds.clear();
            vector <ll> true_lds;
            for (auto x:s){
                auto tmp = upper_bound(lds.begin(),lds.end(),b[x]);
                if (tmp==lds.end()){lds.push_back(b[x]);true_lds.clear();for (auto x:lds)true_lds.push_back(rev[x]);}
                else (*tmp) = b[x];
            }
            sus.push_back(true_lds[0]);
            for (auto x:true_lds)s.erase(x);
            lds.clear();
            for (auto x:s){
                auto tmp = upper_bound(lds.begin(),lds.end(),b[x]);
                if (tmp==lds.end()){lds.push_back(b[x]);true_lds.clear();for (auto x:lds)true_lds.push_back(rev[x]);}
                else (*tmp) = b[x];
            }
            if (sz(s)){
                sus.push_back(true_lds[0]);
            }
            s = pre_s;
            if (sz(sus)==1){
                ans.push_back(MP(a[sus[0]],n+1));
                s.erase(sus[0]);
            }
            else{
                if (sus[0] > sus[1])swap(sus[0],sus[1]);
                if (a[sus[0]] > a[sus[1]]){
                    ans.push_back(MP(a[sus[0]],n+1));
                    s.erase(sus[0]);
                }
                else{
                    ans.push_back(MP(a[sus[0]],a[sus[1]]));
                    s.erase(sus[0]);
                    s.erase(sus[1]);
                }
            }

        }
    }
}
std::vector<std::pair<int, int>> min_shooting_buildings(std::vector<int> H){
    n = sz(H);
    for (ll i = 1;i <= n;i ++)a[i] = H[i-1];
	solve();
	return ans;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3832kb

input:

8
4 3 8 2 1 7 6 5

output:

5
8 9
4 7
3 6
2 5
1 9

result:

wrong answer Incorrect

Subtask #2:

score: 0
Time Limit Exceeded

Test #26:

score: 12
Accepted
time: 0ms
memory: 4064kb

input:

8
5 6 7 1 2 8 3 4

output:

4
6 7
5 8
1 2
3 4

result:

ok Correct

Test #27:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

16
2 4 5 1 9 10 3 6 14 7 8 11 12 16 13 15

output:

8
5 10
4 9
2 14
1 16
3 6
7 8
11 12
13 15

result:

ok Correct

Test #28:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

16
2 3 1 8 12 4 5 6 7 14 15 9 10 16 11 13

output:

8
3 12
2 8
14 15
1 16
4 5
6 7
9 10
11 13

result:

ok Correct

Test #29:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

16
3 5 1 6 8 9 2 11 12 4 7 14 15 10 16 13

output:

8
5 9
3 8
6 12
11 15
14 16
1 2
4 7
10 13

result:

ok Correct

Test #30:

score: 0
Accepted
time: 1ms
memory: 5836kb

input:

16
1 7 2 3 9 11 4 5 6 12 15 8 10 16 13 14

output:

8
7 11
9 15
12 16
1 2
3 4
5 6
8 10
13 14

result:

ok Correct

Test #31:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

16
6 7 8 1 9 2 3 4 11 12 5 10 13 14 15 16

output:

8
8 9
6 7
11 12
1 2
3 4
5 10
13 14
15 16

result:

ok Correct

Test #32:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

16
1 6 2 7 8 9 10 13 3 4 5 11 14 12 16 15

output:

8
6 13
9 10
7 8
14 16
1 2
3 4
5 11
12 15

result:

ok Correct

Test #33:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

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

output:

248
9 10
6 7
5 12
20 24
18 19
15 17
13 33
30 31
27 29
26 39
35 43
34 40
44 47
48 56
53 57
63 65
60 62
71 72
69 77
74 80
92 96
89 90
87 88
81 84
98 102
97 99
105 106
110 112
111 119
114 120
126 127
123 129
132 133
136 144
137 143
150 152
151 156
154 157
158 160
162 167
163 173
169 174
178 183
180 196...

result:

ok Correct

Test #34:

score: 0
Accepted
time: 3ms
memory: 3740kb

input:

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

output:

248
11 13
8 9
5 6
14 16
31 32
26 29
21 24
19 33
39 44
35 41
47 48
51 54
55 58
56 60
59 67
68 74
70 77
76 83
75 81
85 96
94 110
92 107
90 104
89 101
88 100
86 111
112 113
128 129
123 127
121 122
116 119
130 131
133 134
136 138
139 140
142 143
147 156
152 161
148 149
164 165
162 174
173 179
168 175
16...

result:

ok Correct

Test #35:

score: 0
Accepted
time: 3ms
memory: 4088kb

input:

497
6 1 2 10 11 3 12 4 15 5 7 8 16 17 18 19 21 25 26 30 31 9 32 13 14 20 33 35 37 40 41 43 22 45 23 46 24 27 49 50 28 52 53 29 54 58 59 34 36 38 39 42 44 47 61 48 51 63 55 67 68 69 56 57 72 60 62 77 78 79 80 64 65 82 85 87 88 66 89 91 98 102 70 104 71 111 112 113 117 118 120 73 125 129 130 74 75 131...

output:

249
6 11
10 12
15 31
30 32
25 26
19 21
17 18
16 43
41 45
37 40
33 35
46 50
49 53
52 59
54 58
61 63
68 69
67 72
79 80
77 78
88 102
87 98
85 91
82 89
104 120
118 130
117 129
113 125
111 112
131 133
143 147
149 150
148 153
152 168
151 164
163 171
162 170
158 169
156 157
154 155
172 173
178 180
181 182
...

result:

ok Correct

Test #36:

score: 0
Accepted
time: 3ms
memory: 3836kb

input:

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

output:

249
10 11
8 15
2 12
21 22
17 28
27 40
24 35
32 47
31 42
51 52
50 53
59 63
56 61
54 55
67 70
65 69
72 75
76 80
88 91
85 89
81 84
93 98
97 99
94 105
103 107
100 102
110 117
113 118
112 121
119 123
125 130
133 134
137 142
141 144
154 156
147 149
145 161
159 163
168 169
164 165
173 174
172 175
177 183
1...

result:

ok Correct

Test #37:

score: 0
Accepted
time: 3ms
memory: 5848kb

input:

499
5 7 11 12 13 1 17 18 20 22 24 2 3 25 26 27 4 29 31 6 32 33 8 9 10 14 15 34 35 16 19 21 23 28 41 30 36 37 42 45 38 39 46 49 40 50 51 43 52 44 47 48 54 59 53 65 55 67 68 71 56 57 74 75 78 79 58 81 86 87 88 89 60 91 61 98 99 100 102 103 112 62 113 63 114 64 115 116 66 117 69 120 70 121 72 122 124 7...

output:

250
13 24
12 22
11 20
7 18
5 17
27 31
26 29
25 33
32 35
34 41
42 45
49 51
46 50
52 59
54 65
68 71
67 79
78 89
75 88
74 87
86 91
81 112
103 113
100 102
98 99
114 116
115 117
120 121
124 128
122 125
130 133
145 153
143 144
137 161
159 160
155 163
162 164
166 168
178 182
174 176
169 186
191 194
189 190...

result:

ok Correct

Test #38:

score: 0
Accepted
time: 3ms
memory: 3836kb

input:

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

output:

250
18 27
17 23
15 20
12 13
4 10
29 30
28 33
31 35
39 42
38 40
36 37
59 60
56 58
53 55
48 49
65 69
63 66
62 75
71 86
82 83
79 81
78 90
88 92
91 93
99 101
98 100
94 97
108 109
104 105
102 110
112 115
113 118
139 147
138 146
133 140
121 127
120 155
153 156
149 162
160 161
158 159
157 165
166 168
173 1...

result:

ok Correct

Test #39:

score: 0
Accepted
time: 747ms
memory: 6672kb

input:

7495
1 3 5 7 8 2 10 4 11 13 6 14 17 9 21 12 15 23 25 26 16 18 31 19 20 32 35 36 37 42 22 45 46 24 27 28 47 48 49 29 51 52 58 60 30 33 34 38 62 63 39 40 64 65 66 70 72 73 41 74 43 75 77 44 50 53 78 79 54 81 82 55 56 83 57 87 88 89 93 59 61 67 68 97 69 100 102 107 108 110 112 113 118 119 120 71 124 12...

output:

3748
8 10
5 7
3 13
11 17
14 21
25 26
23 31
42 46
37 45
35 36
32 49
48 60
47 58
51 52
62 63
73 74
70 72
65 66
64 77
75 79
78 82
81 83
89 93
87 88
97 120
119 129
118 128
113 125
112 124
108 110
102 107
100 131
134 138
133 137
135 150
146 149
140 142
152 153
151 155
157 161
160 164
166 173
170 181
167 ...

result:

ok Correct

Test #40:

score: 0
Accepted
time: 761ms
memory: 4768kb

input:

7496
4 8 9 14 16 1 19 2 3 5 6 20 21 23 7 25 32 10 33 34 35 36 38 11 39 12 40 13 15 17 43 45 46 47 18 48 51 54 22 58 61 24 62 67 68 26 27 28 72 29 73 75 76 80 30 81 31 37 41 42 82 83 44 85 49 87 50 91 100 52 53 55 56 57 101 103 104 105 106 59 107 109 112 60 63 64 114 122 65 124 66 126 69 70 71 74 127...

output:

3748
16 19
9 14
4 8
23 32
21 25
20 38
36 39
34 35
33 40
47 54
46 51
45 48
43 61
58 68
62 67
72 80
76 81
73 75
83 85
82 87
91 100
106 112
105 109
104 107
101 103
122 124
114 126
127 129
142 143
131 139
146 147
151 153
152 156
155 159
160 161
163 165
166 167
169 177
168 171
180 181
182 185
187 188
191...

result:

ok Correct

Test #41:

score: 0
Accepted
time: 741ms
memory: 4732kb

input:

7497
4 1 7 11 14 15 18 22 2 23 3 5 26 34 35 6 8 36 38 9 10 12 13 39 40 43 44 45 16 17 47 48 49 19 50 57 59 60 20 21 24 25 62 27 28 64 67 68 29 30 31 71 76 77 79 32 81 33 82 84 85 86 87 88 37 41 90 92 93 95 42 96 97 103 105 46 51 52 53 107 108 109 110 54 55 111 112 113 56 115 58 61 63 117 65 118 119 ...

output:

3749
4 22
18 23
14 15
7 11
34 35
26 38
36 45
43 44
39 40
49 60
48 59
47 57
50 62
67 68
64 79
77 81
71 76
87 88
85 86
82 84
95 105
93 103
92 97
90 96
109 110
107 108
113 115
111 112
117 125
122 124
118 119
127 130
128 131
132 149
146 147
143 145
136 138
134 135
150 152
151 153
154 168
158 159
155 172...

result:

ok Correct

Test #42:

score: 0
Accepted
time: 751ms
memory: 6772kb

input:

7498
4 5 6 1 9 2 3 7 8 13 10 16 17 20 21 25 11 26 28 12 14 15 18 19 22 23 24 30 31 27 33 29 32 39 48 34 35 49 36 51 37 54 38 40 55 41 56 42 43 57 58 59 44 61 64 65 45 71 46 47 50 52 72 53 73 77 78 60 62 88 92 93 63 66 95 99 67 68 100 69 70 74 75 101 76 79 102 103 106 80 81 109 115 116 117 82 120 124...

output:

3749
6 9
4 5
13 25
21 28
20 26
16 17
31 33
30 48
39 49
51 54
55 56
59 65
58 64
57 61
71 72
77 78
73 93
88 92
95 99
100 101
103 106
102 117
116 127
115 125
109 124
120 135
134 141
133 139
131 144
143 146
148 151
149 155
154 160
153 158
156 166
165 169
163 164
170 172
181 182
175 177
173 184
183 185
1...

result:

ok Correct

Test #43:

score: 0
Accepted
time: 742ms
memory: 5072kb

input:

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

output:

3750
5 8
3 14
2 22
20 38
26 34
23 25
39 40
41 45
44 59
53 54
46 51
61 62
63 65
64 67
66 83
80 85
73 74
69 72
68 87
88 89
92 93
90 103
101 102
97 106
105 109
111 112
113 117
116 126
125 136
123 135
122 134
119 133
118 132
130 149
147 151
143 145
139 140
137 154
152 155
162 163
157 160
171 177
164 165...

result:

ok Correct

Test #44:

score: 0
Accepted
time: 756ms
memory: 4804kb

input:

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

output:

3750
4 6
18 24
17 23
16 22
14 21
31 32
27 41
39 40
35 44
42 49
52 55
54 58
67 68
61 62
59 72
69 73
88 91
84 85
80 82
75 76
74 95
94 98
93 97
102 108
99 107
113 116
109 112
117 140
134 136
125 132
118 124
141 144
146 148
147 157
153 168
152 163
150 161
159 171
170 172
176 180
174 179
178 182
184 185
...

result:

ok Correct

Test #45:

score: -12
Time Limit Exceeded

input:

99995
4 5 6 8 10 1 11 2 3 14 16 19 21 7 22 9 24 26 27 12 29 31 35 43 13 47 15 17 48 18 51 20 23 25 28 52 53 55 30 56 58 32 60 61 33 34 36 63 37 38 64 65 39 66 70 40 72 77 86 88 89 41 42 44 45 46 91 49 93 94 95 98 100 50 101 54 102 103 57 59 62 67 104 108 68 112 116 117 118 119 69 120 71 73 74 123 12...

output:

Unauthorized output

result:

Subtask #3:

score: 0
Wrong Answer

Test #51:

score: 9
Accepted
time: 0ms
memory: 4036kb

input:

1
1

output:

1
1 2

result:

ok Correct

Test #52:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

2
1 2

output:

1
1 2

result:

ok Correct

Test #53:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

2
2 1

output:

2
2 3
1 3

result:

ok Correct

Test #54:

score: 0
Accepted
time: 1ms
memory: 6072kb

input:

3
1 3 2

output:

2
1 3
2 4

result:

ok Correct

Test #55:

score: 0
Accepted
time: 1ms
memory: 4032kb

input:

3
2 1 3

output:

2
2 3
1 4

result:

ok Correct

Test #56:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

3
2 3 1

output:

2
2 3
1 4

result:

ok Correct

Test #57:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

3
3 1 2

output:

2
3 4
1 2

result:

ok Correct

Test #58:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4
2 1 4 3

output:

2
2 4
1 3

result:

ok Correct

Test #59:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

4
2 4 1 3

output:

2
2 4
1 3

result:

ok Correct

Test #60:

score: 0
Accepted
time: 1ms
memory: 6124kb

input:

4
3 1 4 2

output:

2
3 4
1 2

result:

ok Correct

Test #61:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

4
3 4 1 2

output:

2
3 4
1 2

result:

ok Correct

Test #62:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

3
3 2 1

output:

3
3 4
2 4
1 4

result:

ok Correct

Test #63:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

4
1 4 3 2

output:

3
1 4
3 5
2 5

result:

ok Correct

Test #64:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

4
2 4 3 1

output:

3
2 4
3 5
1 5

result:

ok Correct

Test #65:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

4
3 2 1 4

output:

3
3 4
2 5
1 5

result:

ok Correct

Test #66:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

4
3 2 4 1

output:

3
3 4
2 5
1 5

result:

ok Correct

Test #67:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

4
3 4 2 1

output:

3
3 4
2 5
1 5

result:

ok Correct

Test #68:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

4
4 1 3 2

output:

3
4 5
1 3
2 5

result:

ok Correct

Test #69:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

4
4 2 1 3

output:

3
4 5
2 3
1 5

result:

ok Correct

Test #70:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

4
4 2 3 1

output:

3
4 5
2 3
1 5

result:

ok Correct

Test #71:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

4
4 3 1 2

output:

3
4 5
3 5
1 2

result:

ok Correct

Test #72:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

4
4 3 2 1

output:

4
4 5
3 5
2 5
1 5

result:

ok Correct

Test #73:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

3
1 2 3

output:

2
1 2
3 4

result:

ok Correct

Test #74:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

4
1 2 3 4

output:

2
1 2
3 4

result:

ok Correct

Test #75:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

4
1 2 4 3

output:

2
1 4
2 3

result:

ok Correct

Test #76:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

4
1 3 2 4

output:

2
1 3
2 4

result:

ok Correct

Test #77:

score: -9
Wrong Answer
time: 1ms
memory: 3784kb

input:

4
1 3 4 2

output:

3
1 4
3 5
2 5

result:

wrong answer Incorrect

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 11:05:47 | OpenSource Project