Submission #136385

#	Time	Username	Problem	Language	Result	Execution time	Memory
136385		dndhk	Naan (JOI19_naan)	C++14	100 / 100	779 ms	118244 KiB

naan

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;

ll N, L;
ll arr[MAX_N+1][MAX_N+1];
ll sum[MAX_N+1];

vector<pll> vt[MAX_N+1];
bool vst[MAX_N+1];

vector<pll> ans;
vector<int> ans2;

bool calc(pll a, pll b){
	a.first; b.first;
	a.second /= N; b.second /= N;
	return (a.first * b.second > a.second * b.first);
}

int main(){
	scanf("%lld%lld", &N, &L);
	for(int i=1; i<=N; i++){
		for(int j=1; j<=L; j++){
			scanf("%lld", &arr[i][j]);
			sum[i]+=arr[i][j];
		}
		int now = 1;
		ll S = 0;
		for(int j=1; j<=L; j++){
			while(1){
				//cout<<S<<" "<<now<<endl;
				if((S+arr[i][j]) * N <= now * sum[i]){
					break;
				}
				pll p;
				p.first = sum[i] * now - S * N + (j-1) * N * arr[i][j];
				p.second = N * arr[i][j];
				vt[i].pb(p);
				//cout<<p.first<<" "<<p.second<<endl;
				now++;
			}
			S += arr[i][j];
		}
	}
	for(int i=0; i<N-1; i++){
		pll prv = {1, 0};
		int idx=0;
		for(int j=1; j<=N; j++){
			//cout<<prv.first<<" "<<prv.second<<" "<<vt[j][i].first<<" "<<vt[j][i].second<<endl;
			if(!vst[j] && calc(prv, vt[j][i])){
				idx = j; prv = vt[j][i];
			}
		}
		//cout<<idx<<endl;
		vst[idx] = true;
		ans.pb(prv);
		ans2.pb(idx);
	}
	for(int j=1; j<=N; j++){
		if(!vst[j]){
			ans2.pb(j);
			break;
		}
	}
	for(int i=0; i<ans.size(); i++){
		printf("%lld %lld\n", ans[i].first, ans[i].second);
	}
	for(int i=0; i<ans2.size(); i++){
		printf("%d ", ans2[i]);
	}
	return 0;
}

Compilation message (stderr)

naan.cpp: In function 'bool calc(pll, pll)':
naan.cpp:37:4: warning: statement has no effect [-Wunused-value]
  a.first; b.first;
  ~~^~~~~
naan.cpp:37:13: warning: statement has no effect [-Wunused-value]
  a.first; b.first;
           ~~^~~~~
naan.cpp: In function 'int main()':
naan.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans.size(); i++){
               ~^~~~~~~~~~~
naan.cpp:90:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ans2.size(); i++){
               ~^~~~~~~~~~~~
naan.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &N, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
naan.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &arr[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

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