제출 #229879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229879		xyzyzl	Detecting Molecules (IOI16_molecules)	C++14	69 / 100	55 ms	4984 KiB

molecules

// Time:
// Algorithms: 

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

#define MAXN 1000005

#define FOR(i, n) for (int i = 0; i < n; i++)
#define FORR(j, i, n) for (int i = j; i < n; i++)
#define FORD(i, n) for (int i = n - 1; i >= 0; i--)
#define F1R(i, n) for (int i = 1; i <= n; i++)
#define F1RD(i, n) for (int i = n; i >= 1; i--)
#define pb push_back
#define mp make_pair
#define endl '\n'
#define DUEHOANG                  \
	ios_base::sync_with_stdio(0); \
	cin.tie(NULL);                \
	cout.tie(NULL)

#define fileio(in, out)      \
	freopen(in, "r", stdin); \
	freopen(out, "w", stdout);

#define ll long long
#define MOD (1e9*1)+7
#define MOD2 998244353
#define INF (1e9*1)+5

typedef set<int> si;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<int, pii> iii;
typedef vector<pii> vii;
typedef vector<iii> viii;
typedef priority_queue<int> pqi;
typedef stack<int> sti;
typedef queue<int> qi;
typedef deque<int> di;
typedef map<int, int> mii;
#define f first
#define s second

#define LEFT(x) 2 * x
#define RIGHT(x) 2 * x + 1

#define bitinc(x) x&-x

const int MAX(int &a, int b)
{
	return a = max(a, b); 
}
const int MIN(int &a, int b)
{
	return a = min(a, b); 
}

vi find_subset(int l, int u, vi w)
{
	int n = w.size();
	vii nw(n);
	for(int i = 0; i < w.size(); i++)
	{
		nw[i] = mp(w[i], i);
	}
	sort(nw.begin(), nw.end());
	// you need indices so you kinda can't do this!
	// sort(w.begin(), w.end());
	int i = 0, j = 0, rsm = 0;
	vi ans;
	while(i < n)
	{
		while(i < n && rsm < l)
		{
			rsm += nw[i].f;
			i++;
		}
		while(j < i && rsm > u)
		{
			rsm -= nw[j].f;
			j++;
		}
		if(l <= rsm && rsm <= u)
		{
			// this is good
			for(int k = j; k < i; k++) ans.pb(nw[k].s);
			break;
		}
	}
	// are you supposed to put the subset in inc order too or smth
	// whatever
	sort(ans.begin(), ans.end());
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

molecules.cpp: In function 'vi find_subset(int, int, vi)':
molecules.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < w.size(); i++)
                 ~~^~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 23 / 23
• Subtask 6: 0 / 31