제출 #637294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637294		shmad	코알라 (APIO17_koala)	C++17	99 / 100	50 ms	448 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>

#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvt = vt< vt<int> >;

int a[100], b[100];

int minValue(int n, int w) {  
    fill(a, a + n, 0);
    a[0] = 1;
    playRound(a, b);
    for (int i = 1; i < n; i++) if (b[i] == 0) return i;
    return 0;
}

int maxValue (int n, int w) {
	vt<int> p(n);
	iota(all(p), 0ll);
	while (sz(p) != 1) {
		fill(a, a + n, 0);
		int x = w / sz(p);
		for (int i: p) a[i] = x;
		playRound(a, b);
		p.clear();
		for (int i = 0; i < n; i++) if (b[i] == x + 1) p.pb(i);
	}
    return p[0];
}

int greaterValue (int n, int w) {
	fill(a, a + n, 0);
	int l = 1, r = 13, ans = 0;
	while (l <= r) {
		int mid = l + r >> 1;
		fill(a, a + n, 0);
		a[0] = a[1] = mid;                                               
		playRound(a, b);
		if (b[0] != b[1]) return (b[0] < b[1]);
		if (b[0] > mid && b[1] > mid) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	a[0] = a[1] = ans;
	playRound(a, b);
	return (b[0] < b[1]);
}

bool comp (int i, int j, int n, int w) {
	fill(a, a + n, 0);
	a[i] = a[j] = w / 2;
	playRound(a, b);
	return (b[j] > w / 2);
}

vt<int> merge_sort (vt<int> &v, int n, int w) {
	if (sz(v) == 1) return v;
	vt<int> l, r;
	for (int i = 0; i < sz(v); i++) {
		if (i < sz(v) / 2) l.pb(v[i]);
		else r.pb(v[i]);
	}
	l = merge_sort(l, n, w);
	r = merge_sort(r, n, w);
	v.clear();
	int i = 0, j = 0;
	while (i < sz(l) && j < sz(r)) v.pb((comp(l[i], r[j], n, w) ? l[i++] : r[j++]));
	while (i < sz(l)) v.pb(l[i++]);
	while (j < sz(r)) v.pb(r[j++]);
	return v;
}

void solve (vt<int> &v, int l, int r, int n, int w, int *p) {
	if (l == r) {
    	p[v[0]] = l;
    	return;
    }
    int x = min((int)sqrt(l * 2), w / (r - l + 1));
    fill(a, a + n, 0);
    for (int i: v) a[i] = x;
    playRound(a, b);
    vt<int> L, R;
    for (int i: v) {
    	if (b[i] == x + 1) R.pb(i);
    	else L.pb(i);
    }
    solve(L, l, l + sz(L) - 1, n, w, p);
    solve(R, r - sz(R) + 1, r, n, w, p);
}

void allValues (int n, int w, int *p) {
    vt<int> v(n);
    iota(all(v), 0);	
    if (w == n * 2) {
        v = merge_sort(v, n, w);
    	for (int i = 0; i < n; i++) p[v[i]] = i + 1;
    	return;
    }
    solve(v, 1, n, n, w, p);
    playRound(a, b);
    playRound(a, b);
    playRound(a, b);
}

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

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:46:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid = l + r >> 1;
      |             ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 52 / 53