제출 #524426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524426		ymm	Naan (JOI19_naan)	C++17	24 / 100	1 ms	464 KiB

naan

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;


const int N = 2022;
ll v[N][N]; ll ps[N][N];
bool done[N];
ll n, m;
ll den;

ll get(ll l, ll r, int i){
	return (ps[i][r/den]-ps[i][l/den])*den + (r%den)*v[i][r/den] - (l%den)*v[i][l/den];
}

ll nxt(ll f, int i){
	ll l=f, r=den*m+1;
	while(l<r){
		ll mid = (l+r)/2;
		if(get(f,mid,i)>=ps[i][m]*den/n) r=mid;
		else                             l=mid+1;
	}
	return l;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	den = n*m*2520;
	Loop(i,0,n) Loop(j,0,m){
		cin >> v[i][j];
		ps[i][j+1] = ps[i][j]+v[i][j];
	}
	ll cur = 0;
	vector<pair<ll,int>> vec;
//	cout << get(0,28,1) << "?\n";
	Loop(i,0,n) {
		ll mn = den*m+1;
		int mni = -1;
		Loop(j,0,n){
			if(done[j]) continue;
			ll f = nxt(cur, j);
			if(f < mn && get(cur,f,j) == ps[j][m]*den/n){
				mn = f;
				mni = j;
			}
		}
		if(mni==-1) {
			Loop(j,0,n){
				if(done[j]) continue;
				ll f = nxt(cur, j);
				if(f < mn){
					mn = f;
					mni = j;
				}
			}
		}
		if(mni==-1) Kill(-1);
		done[mni]=1;
		vec.push_back({mn,mni});
		cur=mn;
//		cout << mn<<' '<<mni << "!\n";
	}
	Loop(i,0,n-1){
		cout << vec[i].first << ' ' << den << '\n';
	}
	Loop(i,0,n) cout << vec[i].second+1 << ' ';
	cout << '\n';
}

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