Submission #170767

#	Time	Username	Problem	Language	Result	Execution time	Memory
170767		songc	Naan (JOI19_naan)	C++14	100 / 100	640 ms	103888 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;

int N, M;
bool chk[2020];
LL V[2020][2020];
pll C[2020][2020];
vector<int> P;

bool comp(pll a, pll b){
	return (__int128)a.first*b.second < (__int128)a.second*b.first;
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) scanf("%d", &V[i][j]);
	for (int i=1; i<=N; i++){
		LL S=0, sum=V[i][1];
		for (int j=1; j<=M; j++) S += V[i][j];

		int t=1;
		for (int j=1; j<=N; j++){
			while (sum*N < S*j){
				t++;
				sum += V[i][t];
			}
			LL p = S*j-N*sum+V[i][t]*N*t;
			LL q = V[i][t] * N;
			C[i][j] = pll(p, q);
		}
	}
	for (int i=1; i<N; i++){
		pll Min=pll(1234567890123456ll, 1);
		int k=0;

		for (int j=1; j<=N; j++) if (!chk[j] && comp(C[j][i], Min)) Min = C[j][i], k = j;
		printf("%lld %lld\n", Min.first, Min.second);
		P.push_back(k);
		chk[k] = true;
	}
	for (int x : P) printf("%d ", x);
	for (int i=1; i<=N; i++) if (!chk[i]) printf("%d\n", i);
	return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:18:72: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'LL* {aka long long int*}' [-Wformat=]
  for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) scanf("%d", &V[i][j]);
                                                                ~~~~~~~~^
naan.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:18:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) for (int j=1; j<=M; j++) scanf("%d", &V[i][j]);
                                                    ~~~~~^~~~~~~~~~~~~~~~

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