Submission #00008

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 28;
int N, M, D[99999];
vector< int > Data;
int root;
int ChildIdx[200000];
int Mid3Minimum(int idx, const int value)
{
if(~ChildIdx[idx]) {
int Cost[3] = {Mid3Minimum(ChildIdx[idx], value),
Mid3Minimum(ChildIdx[idx] + 1, value),
Mid3Minimum(ChildIdx[idx] + 2, value)};
sort(Cost, Cost + 3);
return(min(Cost[0] + Cost[1], INF));
} else {
if(D[idx] >= value) return(0);
else if(D[idx] > 0) return(INF);
else return(1);
}
}
void MakeTreeArray()
{
memset(ChildIdx, -1, sizeof(ChildIdx));
queue< int > que;
for(int i = 0; i < N; i++) que.push(i);
root = N;
while(que.size() > 1) {
ChildIdx[root] = que.front();
que.push(root++);
que.pop();
que.pop();
que.pop();
}
--root;
}
int main()
{
vector< int > nums;
cin >> N >> M;
MakeTreeArray();
for(int i = 0; i < M; i++) {
int d, p;
cin >> d >> p;
D[--p] = d;
nums.push_back(d);
}
for(int i = 0; i < N - M; i++) {
int d;
cin >> d;
Data.push_back(d);
nums.push_back(d);
}
sort(Data.begin(), Data.end());
sort(nums.begin(), nums.end());
int low = 0, high = nums.size() - 1;
while(high - low > 0) {
int mid = (low + high + 1) >> 1;
if(Mid3Minimum(root, nums[mid]) <= nums.size() - mid) low = mid;
else high = mid - 1;
}
cout << nums[low] << endl;
}

ステータス

項目 データ
問題 0002 - 舞踏会 (Ball)
ユーザー名 ei1333
投稿日時 2016-01-20 17:39:53
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 1506 Byte
最大実行時間 143 ms
最大メモリ使用量 2956 KB

セット

セット 得点 Cases
1 Subtask1 0 / 8 sample-*, 01-*
2 Subtask2 0 / 16 sample-*, 01-*, 02-*
3 Subtask3 0 / 44 sample-*, 01-*, 02-*, 03-*
4 Subtask4 0 / 32 sample-*, 01-*, 02-*, 03-*, 04-*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.txt WA 143 ms 1244 KB
1
2
3
4
01-02.txt AC 11 ms 1456 KB
1
2
3
4
01-03.txt WA 11 ms 1408 KB
1
2
3
4
01-04.txt WA 13 ms 1232 KB
1
2
3
4
01-05.txt WA 14 ms 1308 KB
1
2
3
4
01-06.txt WA 11 ms 1264 KB
1
2
3
4
01-07.txt WA 12 ms 1344 KB
1
2
3
4
01-08.txt WA 13 ms 1296 KB
1
2
3
4
01-09.txt WA 12 ms 1248 KB
1
2
3
4
01-10.txt WA 14 ms 1332 KB
1
2
3
4
01-11.txt WA 12 ms 1284 KB
1
2
3
4
01-12.txt WA 13 ms 1364 KB
1
2
3
4
01-13.txt WA 10 ms 1448 KB
1
2
3
4
01-14.txt AC 13 ms 1400 KB
1
2
3
4
01-15.txt AC 10 ms 1356 KB
1
2
3
4
01-16.txt WA 12 ms 1308 KB
1
2
3
4
01-17.txt AC 12 ms 1388 KB
1
2
3
4
01-18.txt WA 13 ms 1212 KB
1
2
3
4
01-19.txt WA 11 ms 1292 KB
1
2
3
4
01-20.txt WA 14 ms 1372 KB
1
2
3
4
02-01.txt WA 11 ms 1452 KB
2
3
4
02-02.txt WA 15 ms 1404 KB
2
3
4
02-03.txt AC 11 ms 1488 KB
2
3
4
02-04.txt WA 11 ms 1440 KB
2
3
4
02-05.txt AC 10 ms 1392 KB
2
3
4
02-06.txt AC 11 ms 1344 KB
2
3
4
02-07.txt AC 10 ms 1428 KB
2
3
4
02-08.txt WA 11 ms 1380 KB
2
3
4
02-09.txt AC 10 ms 1336 KB
2
3
4
02-10.txt AC 11 ms 1416 KB
2
3
4
02-11.txt AC 14 ms 1492 KB
2
3
4
02-12.txt AC 13 ms 1316 KB
2
3
4
02-13.txt WA 14 ms 1396 KB
2
3
4
02-14.txt WA 11 ms 1348 KB
2
3
4
02-15.txt AC 11 ms 1424 KB
2
3
4
03-01.txt WA 14 ms 1252 KB
3
4
03-02.txt WA 12 ms 1332 KB
3
4
03-03.txt AC 12 ms 1404 KB
3
4
03-04.txt WA 13 ms 1472 KB
3
4
03-05.txt AC 14 ms 1408 KB
3
4
03-06.txt WA 13 ms 1476 KB
3
4
03-07.txt AC 15 ms 1536 KB
3
4
03-08.txt AC 16 ms 1600 KB
3
4
03-09.txt AC 15 ms 1404 KB
3
4
03-10.txt WA 16 ms 1328 KB
3
4
03-11.txt WA 13 ms 1384 KB
3
4
03-12.txt WA 12 ms 1436 KB
3
4
03-13.txt WA 11 ms 1500 KB
3
4
03-14.txt AC 14 ms 1560 KB
3
4
03-15.txt WA 11 ms 1504 KB
3
4
04-01.txt WA 49 ms 2540 KB
4
04-02.txt WA 55 ms 2720 KB
4
04-03.txt WA 59 ms 2696 KB
4
04-04.txt AC 81 ms 2472 KB
4
04-05.txt AC 74 ms 2640 KB
4
04-06.txt WA 60 ms 2892 KB
4
04-07.txt WA 64 ms 2956 KB
4
04-08.txt WA 58 ms 2880 KB
4
04-09.txt WA 60 ms 2920 KB
4
04-10.txt AC 56 ms 2768 KB
4
04-11.txt AC 84 ms 2452 KB
4
04-12.txt WA 71 ms 2868 KB
4
04-13.txt WA 73 ms 2760 KB
4
04-14.txt AC 77 ms 2728 KB
4
04-15.txt WA 75 ms 2736 KB
4
sample-01.txt AC 15 ms 1528 KB
1
2
3
4
sample-02.txt AC 12 ms 1484 KB
1
2
3
4
sample-03.txt AC 11 ms 1568 KB
1
2
3
4