제출 #721210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
721210		jk410	Naan (JOI19_naan)	C++17	100 / 100	401 ms	110472 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct frac {
	ll x, u, d;//x+u/d 꼴을 나타냄
};
bool operator<(const frac& a, const frac& b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.u * b.d < b.u* a.d;
}
int N, L;
ll V[2001];
frac X[2001][2000];
bool Used[2001];
int P[2001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> L;
	for (int i = 1; i <= N; i++) {
		ll sum = 0;
		for (int j = 1; j <= L; j++) {
			cin >> V[j];
			sum += V[j];
		}
		ll cur = 0;
		for (int j = 1, k = 1; j < N; j++) {
			while ((cur + V[k]) * N <= sum * j)
				cur += V[k++];
			X[i][j] = { k - 1,sum * j - N * cur,N * V[k] };
		}
	}
	vector<pair<ll, ll>> ans;
	for (int i = 1; i < N; i++) {
		int idx;
		frac mn = { L,0,1 };
		for (int j = 1; j <= N; j++) {
			if (Used[j])
				continue;
			if (X[j][i] < mn) {
				mn = X[j][i];
				idx = j;
			}
		}
		ans.push_back({ mn.x * mn.d + mn.u,mn.d });
		P[i] = idx;
		Used[idx] = true;
	}
	for (int i = 1; i <= N; i++) {
		if (!Used[i])
			P[N] = i;
	}
	for (auto i : ans)
		cout << i.first << " " << i.second << "\n";
	for (int i = 1; i <= N; i++)
		cout << P[i] << " ";
	return 0;
}

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

naan.cpp: In function 'int main()':
naan.cpp:49:13: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   Used[idx] = true;
      |   ~~~~~~~~~~^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71