Submission #171548

#	Time	Username	Problem	Language	Result	Execution time	Memory
171548		dennisstar	Naan (JOI19_naan)	C++11	29 / 100	72 ms	23520 KiB

naan

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int N, L;
int V[2010][2010], S[2010], chk[2010];
vector<pll> ar[2010];
vector<pair<pll, int> > VP;
vim ans;

bool cmp(pll a, pll b) {return a.fi*b.se<b.fi*a.se;}
bool cmp1(pair<pll, int> a, pair<pll, int> b) {return a.fi.fi*b.fi.se<=b.fi.fi*a.fi.se;}

int main() {
	scanf("%d %d", &N, &L);
	for (int i=1; i<=N; i++) for (int j=1; j<=L; j++) {
		scanf("%d", &V[i][j]);
		V[i][j]*=N;
		S[i]+=V[i][j];
	}
	ll s;
	for (int i=1; i<=N; i++) {
		s=0;
		ar[i].push_back({0,1});
		for (int j=1, k=1; j<=L; j++) {
			s+=V[i][j];
			while (k<=N && k*(S[i]/N)<=s) {
				ar[i].push_back({(j-1)*V[i][j]+k*(S[i]/N)-(s-V[i][j]) , V[i][j]});
				k++;
			}
		}
	}
	pll lst={0, 1};
	for (int i=0; i<N; i++) {
		VP.clear();
		for (int j=1; j<=N; j++) {
			if (chk[j]) continue;
			int lb=lower_bound(all(ar[j]), lst, cmp)-ar[j].begin();
			VP.push_back({ar[j][lb+1], j});
		}
		sort(all(VP), cmp1);
		if (i!=N-1) printf("%lld %lld\n", VP[0].fi.fi, VP[0].fi.se);
		ans.push_back(VP[0].se);
		chk[VP[0].se]=1;
		lst=VP[0].fi;
	}
	for (int i:ans) printf("%d ", i);
	puts("");
	return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &V[i][j]);
   ~~~~~^~~~~~~~~~~~~~~~

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