QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #375644 | #4088. 총 쏘기 | hotboy2703 | 0 | 243ms | 5844kb | C++14 | 2.1kb | 2024-04-03 14:30:21 | 2024-04-03 14:30:22 |
Judging History
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)){
vector <ll> sus;
lds.clear();
ll tmp_sus = 0;
for (auto x:s){
auto tmp = upper_bound(lds.begin(),lds.end(),b[x]);
if (tmp==lds.end()){lds.push_back(b[x]);tmp_sus = rev[lds[0]];}
else (*tmp) = b[x];
}
if (tmp_sus){
sus.push_back(tmp_sus);
s.erase(tmp_sus);
tmp_sus = 0;
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]);tmp_sus = rev[lds[0]];}
else (*tmp) = b[x];
}
if (tmp_sus){
sus.push_back(tmp_sus);
s.erase(tmp_sus);
}
}
if (sz(sus)==1){
ans.push_back(MP(a[sus[0]],n+1));
}
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.insert(sus[1]);
}
else{
ans.push_back(MP(a[sus[0]],a[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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 17
Accepted
time: 1ms
memory: 5816kb
input:
8 4 3 8 2 1 7 6 5
output:
4 4 8 3 7 2 6 1 5
result:
ok Correct
Test #2:
score: -17
Wrong Answer
time: 1ms
memory: 3784kb
input:
16 12 16 11 15 10 9 8 4 14 13 7 2 6 5 3 1
output:
13 16 17 15 17 14 17 12 13 11 17 10 17 9 17 8 17 7 17 6 17 4 5 2 3 1 17
result:
wrong answer Incorrect
Subtask #2:
score: 0
Time Limit Exceeded
Test #26:
score: 12
Accepted
time: 1ms
memory: 3784kb
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: 3808kb
input:
16 2 4 5 1 9 10 3 6 14 7 8 11 12 16 13 15
output:
8 4 5 2 10 9 14 1 16 3 6 7 8 11 12 13 15
result:
ok Correct
Test #28:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
16 2 3 1 8 12 4 5 6 7 14 15 9 10 16 11 13
output:
8 2 3 8 12 14 15 1 16 4 5 6 7 9 10 11 13
result:
ok Correct
Test #29:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
16 3 5 1 6 8 9 2 11 12 4 7 14 15 10 16 13
output:
8 3 5 8 9 6 12 11 15 14 16 1 2 4 7 10 13
result:
ok Correct
Test #30:
score: 0
Accepted
time: 0ms
memory: 3864kb
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 7 8 6 9 11 12 1 2 3 4 5 10 13 14 15 16
result:
ok Correct
Test #32:
score: 0
Accepted
time: 0ms
memory: 3812kb
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: 1ms
memory: 4108kb
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 34 35 40 43 44 47 48 56 53 57 63 65 60 62 69 71 72 77 74 80 90 92 88 89 84 87 81 96 97 98 99 102 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: 1ms
memory: 4068kb
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 29 31 24 26 19 21 32 33 35 39 41 44 47 48 51 54 55 58 56 60 59 67 68 74 70 77 75 76 81 83 85 96 92 94 89 90 86 88 107 110 101 104 100 111 112 113 127 128 122 123 119 121 116 129 130 131 133 134 136 138 139 140 142 143 147 156 149 152 148 161 162 164 165 174 168 173 166 179 17...
result:
ok Correct
Test #35:
score: 0
Accepted
time: 2ms
memory: 4112kb
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 26 30 21 25 18 19 16 17 32 43 40 41 35 37 33 45 46 50 49 53 52 59 54 58 61 63 68 69 67 72 79 80 77 78 87 88 82 85 98 102 89 91 104 120 117 118 112 113 111 130 125 129 131 133 143 147 149 150 148 153 151 152 164 168 162 163 157 158 155 156 154 171 169 170 172 173 178 180 181 182 ...
result:
ok Correct
Test #36:
score: 0
Accepted
time: 1ms
memory: 4068kb
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 2 8 12 15 17 21 22 28 24 27 35 40 31 32 42 47 50 51 52 53 56 59 54 55 61 63 65 67 69 70 72 75 76 80 85 88 81 84 89 91 93 98 94 97 99 105 102 103 100 107 110 117 112 113 118 121 119 123 125 130 133 134 137 142 141 144 149 154 145 147 156 161 159 163 168 169 164 165 173 174 172 175 176 177 1...
result:
ok Correct
Test #37:
score: 0
Accepted
time: 1ms
memory: 3824kb
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 12 13 7 11 5 24 20 22 17 18 26 27 25 31 29 33 32 35 34 41 42 45 46 49 50 51 52 59 54 65 68 71 67 79 75 78 74 89 87 88 81 86 91 112 102 103 99 100 98 113 114 116 115 117 120 121 122 124 125 128 130 133 144 145 137 143 153 161 159 160 155 163 162 164 166 168 176 178 169 174 182 186 191 194 189 190...
result:
ok Correct
Test #38:
score: 0
Accepted
time: 1ms
memory: 3820kb
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 17 18 13 15 10 12 4 27 20 23 28 29 30 33 31 35 38 39 36 37 40 42 59 60 56 58 53 55 48 49 63 65 62 69 66 75 71 86 82 83 79 81 78 90 88 92 91 93 98 99 94 97 100 101 105 108 102 104 109 110 112 115 113 118 138 139 127 133 120 121 146 147 140 155 149 153 156 162 160 161 158 159 157 165 166 168 173 1...
result:
ok Correct
Test #39:
score: 0
Accepted
time: 243ms
memory: 4412kb
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 7 8 3 5 10 13 11 17 14 21 25 26 23 31 37 42 35 36 32 46 45 49 47 48 58 60 51 52 62 63 72 73 66 70 64 65 74 77 75 79 78 82 81 83 89 93 87 88 97 120 118 119 112 113 108 110 102 107 100 129 125 128 124 131 133 134 137 138 135 150 146 149 140 142 152 153 151 155 157 161 160 164 166 173 167 170 177 ...
result:
ok Correct
Test #40:
score: 0
Accepted
time: 243ms
memory: 4384kb
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 14 16 8 9 4 19 21 23 20 32 25 38 35 36 33 34 39 40 46 47 43 45 51 54 48 61 58 68 62 67 72 80 75 76 73 81 82 83 85 87 91 100 105 106 103 104 101 112 107 109 114 122 124 126 127 129 142 143 131 139 146 147 151 153 152 156 155 159 160 161 163 165 166 167 168 169 171 177 180 181 182 185 187 188 191...
result:
ok Correct
Test #41:
score: 0
Accepted
time: 243ms
memory: 4452kb
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 15 18 11 14 7 23 34 35 26 38 36 45 43 44 39 40 48 49 47 60 57 59 50 62 67 68 64 79 76 77 71 81 87 88 85 86 82 84 93 95 90 92 103 105 96 97 109 110 107 108 112 113 111 115 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: 243ms
memory: 4420kb
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 5 6 4 9 13 25 20 21 16 17 26 28 30 31 33 48 39 49 51 54 55 56 58 59 57 65 61 64 71 72 77 78 73 93 88 92 95 99 100 101 103 106 102 117 115 116 109 127 124 125 120 135 133 134 131 141 139 144 143 146 148 151 149 155 153 154 158 160 156 166 164 165 163 169 170 172 177 181 173 175 182 184 183 185 1...
result:
ok Correct
Test #43:
score: 0
Accepted
time: 239ms
memory: 4388kb
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 3 5 2 8 14 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 74 80 72 73 68 69 85 87 88 89 92 93 90 103 101 102 97 106 105 109 111 112 113 117 116 126 123 125 119 122 118 136 134 135 132 133 130 149 145 147 140 143 137 139 151 154 152 155 160 162 157 163 165 171 164 177...
result:
ok Correct
Test #44:
score: 0
Accepted
time: 239ms
memory: 4688kb
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 17 18 14 16 23 24 21 22 27 31 32 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 93 94 97 98 99 102 107 108 113 116 109 112 117 140 134 136 125 132 118 124 141 144 146 148 147 157 152 153 150 168 161 163 159 171 170 172 174 176 179 180 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: 3784kb
input:
1 1
output:
1 1 2
result:
ok Correct
Test #52:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
2 1 2
output:
1 1 2
result:
ok Correct
Test #53:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
2 2 1
output:
2 2 3 1 3
result:
ok Correct
Test #54:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 1 3 2
output:
2 1 3 2 4
result:
ok Correct
Test #55:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 2 1 3
output:
2 2 4 1 3
result:
ok Correct
Test #56:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
3 2 3 1
output:
2 2 3 1 4
result:
ok Correct
Test #57:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
3 3 1 2
output:
2 3 4 1 2
result:
ok Correct
Test #58:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
4 2 1 4 3
output:
2 2 4 1 3
result:
ok Correct
Test #59:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
4 2 4 1 3
output:
2 2 4 1 3
result:
ok Correct
Test #60:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
4 3 1 4 2
output:
2 3 4 1 2
result:
ok Correct
Test #61:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
4 3 4 1 2
output:
2 3 4 1 2
result:
ok Correct
Test #62:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
3 3 2 1
output:
3 3 4 2 4 1 4
result:
ok Correct
Test #63:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 1 4 3 2
output:
3 4 5 1 3 2 5
result:
ok Correct
Test #64:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 2 4 3 1
output:
3 4 5 2 3 1 5
result:
ok Correct
Test #65:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
4 3 2 1 4
output:
3 3 5 2 5 1 4
result:
ok Correct
Test #66:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
4 3 2 4 1
output:
3 3 4 2 5 1 5
result:
ok Correct
Test #67:
score: 0
Accepted
time: 1ms
memory: 5820kb
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: 3784kb
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: 5824kb
input:
4 4 2 1 3
output:
3 4 5 2 5 1 3
result:
ok Correct
Test #70:
score: 0
Accepted
time: 0ms
memory: 3736kb
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: 3676kb
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: 5844kb
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: 0ms
memory: 3784kb
input:
3 1 2 3
output:
2 1 2 3 4
result:
ok Correct
Test #74:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4 1 2 3 4
output:
2 1 2 3 4
result:
ok Correct
Test #75:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
4 1 2 4 3
output:
2 1 4 2 3
result:
ok Correct
Test #76:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
4 1 3 2 4
output:
2 1 3 2 4
result:
ok Correct
Test #77:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 1 3 4 2
output:
2 3 4 1 2
result:
ok Correct
Test #78:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
4 1 4 2 3
output:
2 1 4 2 3
result:
ok Correct
Test #79:
score: -9
Wrong Answer
time: 0ms
memory: 3808kb
input:
4 2 1 3 4
output:
3 2 5 1 3 4 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%