QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#375658	#4088. 총 쏘기	hotboy2703	0	761ms	6772kb	C++14	2.2kb	2024-04-03 14:36:05	2024-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;
}

源文件, 语言: C++14

详细

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

result:

ok Correct

Test #63:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

4
1 4 3 2

output:

result:

ok Correct

Test #64:

score: 0

Accepted

time: 0ms

memory: 3752kb

input:

4
2 4 3 1

output:

result:

ok Correct

Test #65:

score: 0

Accepted

time: 1ms

memory: 3728kb

input:

4
3 2 1 4

output:

result:

ok Correct

Test #66:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

4
3 2 4 1

output:

result:

ok Correct

Test #67:

score: 0

Accepted

time: 0ms

memory: 3788kb

input:

4
3 4 2 1

output:

result:

ok Correct

Test #68:

score: 0

Accepted

time: 0ms

memory: 3848kb

input:

4
4 1 3 2

output:

result:

ok Correct

Test #69:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

4
4 2 1 3

output:

result:

ok Correct

Test #70:

score: 0

Accepted

time: 0ms

memory: 3752kb

input:

4
4 2 3 1

output:

result:

ok Correct

Test #71:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

4
4 3 1 2

output:

result:

ok Correct

Test #72:

score: 0

Accepted

time: 0ms

memory: 3748kb

input:

4
4 3 2 1

output:

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:

result:

wrong answer Incorrect

Subtask #4:

score: 0

Skipped

Dependency #3:

Subtask #5:

score: 0

Skipped

Dependency #4:

Subtask #6:

score: 0

Skipped

Dependency #5:

Subtask #7:

score: 0

Skipped