답안 #137077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137077	2019-07-27T04:28:00 Z	anayk	Detecting Molecules (IOI16_molecules)	C++14	9 / 100	2 ms	376 KB

molecules

#include "molecules.h"

#include <vector>
#include <algorithm>

#define MAXN 200005

int n;
std::vector<int> answer;
bool choice[MAXN];
std::pair<int, int> vals[MAXN];
int rev[MAXN];

void make()
{
	for(int i = 0; i < n; i++)
		if(choice[i])
			answer.push_back(rev[i]);
}

std::vector<int> find_subset(int l, int u, std::vector<int> w)
{
	n = w.size();
	
	for(int i = 0; i < n; i++)
	{
		vals[i].first = w[i];
		vals[i].second = i;
		choice[i] = false;
	}
	
	std::sort(vals, vals+n);
	
	for(int i = 0; i < n; i++)
	{
		w[i] = vals[i].first;
		rev[i] = vals[i].second;
	}
	
	int cur = 0;
	int low = 0; int high = 0;
	bool poss = false;
	for(int i = 0; i < n; i++)
	{
		low += w[i];
		high += w[n-1-i];
		choice[n-1-i] = true;
		
		if(high >= l && low <= u)
		{
			poss = true;
			break;
		}
	}
	
	if(!poss)
		return answer;
	
	if(cur <= u)
	{
		make();
		return answer;
	}
	
	int x = 0; int y = n-1;
	while(x < y)
	{
		if(choice[x])
		{
			x++;
			continue;
		}
		
		if(!choice[y])
		{
			y--;
			continue;
		}
		
		choice[x] = true;
		choice[y] = false;
		
		cur += w[x] - w[y];
		
		if(cur <= u)
		{
			make();
			return answer;
		}
	}
	
	if(cur - w[0] >= l)
	{
		choice[0] = true;
		make();
	}
	
	return answer;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	OK (n = 1, answer = NO)
2	Correct	2 ms	256 KB	OK (n = 1, answer = NO)
3	Correct	2 ms	256 KB	OK (n = 1, answer = YES)
4	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
5	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
6	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
7	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
8	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
9	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
10	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
11	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
12	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
13	Correct	2 ms	376 KB	OK (n = 3, answer = NO)
14	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
15	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
16	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
17	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
18	Correct	2 ms	256 KB	OK (n = 100, answer = NO)
19	Correct	2 ms	256 KB	OK (n = 100, answer = YES)

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	256 KB	sum of weights should be in [302..304] but it is 306
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	OK (n = 1, answer = NO)
2	Correct	2 ms	256 KB	OK (n = 1, answer = NO)
3	Correct	2 ms	256 KB	OK (n = 1, answer = YES)
4	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
5	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
6	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
7	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
8	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
9	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
10	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
11	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
12	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
13	Correct	2 ms	376 KB	OK (n = 3, answer = NO)
14	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
15	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
16	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
17	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
18	Correct	2 ms	256 KB	OK (n = 100, answer = NO)
19	Correct	2 ms	256 KB	OK (n = 100, answer = YES)
20	Incorrect	2 ms	256 KB	sum of weights should be in [302..304] but it is 306
21	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	OK (n = 1, answer = NO)
2	Correct	2 ms	256 KB	OK (n = 1, answer = NO)
3	Correct	2 ms	256 KB	OK (n = 1, answer = YES)
4	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
5	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
6	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
7	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
8	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
9	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
10	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
11	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
12	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
13	Correct	2 ms	376 KB	OK (n = 3, answer = NO)
14	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
15	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
16	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
17	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
18	Correct	2 ms	256 KB	OK (n = 100, answer = NO)
19	Correct	2 ms	256 KB	OK (n = 100, answer = YES)
20	Incorrect	2 ms	256 KB	sum of weights should be in [302..304] but it is 306
21	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	OK (n = 1, answer = NO)
2	Correct	2 ms	256 KB	OK (n = 1, answer = NO)
3	Correct	2 ms	256 KB	OK (n = 1, answer = YES)
4	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
5	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
6	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
7	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
8	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
9	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
10	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
11	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
12	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
13	Correct	2 ms	376 KB	OK (n = 3, answer = NO)
14	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
15	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
16	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
17	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
18	Correct	2 ms	256 KB	OK (n = 100, answer = NO)
19	Correct	2 ms	256 KB	OK (n = 100, answer = YES)
20	Incorrect	2 ms	256 KB	sum of weights should be in [302..304] but it is 306
21	Halted	0 ms	0 KB	-

Subtask #6

0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	OK (n = 1, answer = NO)
2	Correct	2 ms	256 KB	OK (n = 1, answer = NO)
3	Correct	2 ms	256 KB	OK (n = 1, answer = YES)
4	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
5	Correct	2 ms	256 KB	OK (n = 2, answer = YES)
6	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
7	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
8	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
9	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
10	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
11	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
12	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
13	Correct	2 ms	376 KB	OK (n = 3, answer = NO)
14	Correct	2 ms	256 KB	OK (n = 3, answer = YES)
15	Correct	2 ms	376 KB	OK (n = 3, answer = YES)
16	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
17	Correct	2 ms	256 KB	OK (n = 3, answer = NO)
18	Correct	2 ms	256 KB	OK (n = 100, answer = NO)
19	Correct	2 ms	256 KB	OK (n = 100, answer = YES)
20	Incorrect	2 ms	256 KB	sum of weights should be in [302..304] but it is 306
21	Halted	0 ms	0 KB	-