Submission #209369

#	Time	Username	Problem	Language	Result	Execution time	Memory
209369		erd1	Naan (JOI19_naan)	C++14	100 / 100	1722 ms	81144 KiB

naan

#include<bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<lld, int> pli;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
template<typename It>
ostream& _out(ostream& out, It b, It e){
    for(It i = b; i != e; i++){
        if(i != b)out << ' ';
        out << *i;
    }
}
template<typename T>
ostream& operator<<(ostream& out, vector<T>& v){
    return _out(out<<'[', all(v)) << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
    return out << '(' << p.ff << ", " << p.ss << ')';
}
vector<vector<int>> g;
vector<vector<pli>> v;
vector<int> perms;
vector<pli> ans;
vector<bool> used;
bool comp(pli a, pli b){
    if(a.ff/a.ss == b.ff/b.ss)
        return a.ff%a.ss*b.ss < b.ff%b.ss*a.ss;
    return a.ff/a.ss < b.ff/b.ss;
}
signed main(){
	int n, m;
	cin >> n >> m;
	g.resize(n), v.resize(n), used.resize(n);
	for(int i = 0; i < n; i++){
		int sum = 0;
		g[i].resize(m);
		for(int j = 0; j < m; j++){
			cin >> g[i][j];
			sum += g[i][j];
		}
		for(int j = 0, s = 0, k = 1; j < m; j++){
        while((lld)(s+g[i][j])*n >= (lld)k*sum)v[i].pb({(lld)k*sum-(lld)s*n+(lld)j*g[i][j]*n, g[i][j]*n}), k++; //(k*sum/n-s)/g[i][j]+j
			s += g[i][j];
		}
	}
	for(int i = 0; i < n; i++){
        pli minx = {LLONG_MAX, 1};
        int mini = 0;
        for(int j = 0; j < n; j++){
            if(used[j])continue;
            if(comp(v[j][i], minx))minx = v[j][i], mini = j;
        }
        used[mini] = true;
        perms.pb(mini+1), ans.pb(minx);
	}
	for(int i = 0; i < n-1; i++)cout << ans[i].ff << " " << ans[i].ss << endl;
	for(int i = 0; i < n; i++)cout << perms[i] << " ";
	cout <<endl;
}

Compilation message (stderr)

naan.cpp: In function 'std::ostream& _out(std::ostream&, It, It)':
naan.cpp:15:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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