Submission #1170122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170122		miniob	Naan (JOI19_naan)	C++20	29 / 100	46 ms	11076 KiB

naan

#include <bits/stdc++.h>
using namespace std;

long long war[2007][2007];
__int128 pref[2007][2007];
__int128 potrz[2007];
bool czy_juz[2007];
__int128 gdzie_jestem[2007];

__int128 nastepny(pair<__int128, __int128> cur, __int128 nowe)
{
	return (max((cur.first * nowe + cur.second - 1), (__int128)0) / max(cur.second, (__int128)1));
}

int main() 
{
	long long n, l;
	cin >> n >> l;
	vector<long long> per;
	vector<pair<long long, long long>> miejsca;
	for(__int128 i = 1; i <= n; i++)
	{
		for(__int128 j = 1; j <= l; j++)
		{
			cin >> war[i][j];
			potrz[i] += war[i][j];
			war[i][j] *= n;
			pref[i][j] = pref[i][j - 1] + war[i][j];
			//cout << pref[i][j] << " ";
		}
		//cout << endl;
	}
	__int128 pop_calk, curmin, ktory;
	pair<__int128, __int128> pop, curminu, temp;
	pop = {0, 0};
	pop_calk = 0;
	for(__int128 i = 1; i < n; i++)
	{
		curmin = LLONG_MAX;
		for(__int128 j = 1; j <= n; j++)
		{
			if(!czy_juz[j])
			{
				while(gdzie_jestem[j] <= l && pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j] + 1]) < potrz[j])
				{
					/*if(j == 3)
					{
						cout << gdzie_jestem[j] << endl;
					}*/
					//cout << gdzie_jestem[j] << endl;
					//cout << nastepny(pop, war[j][gdzie_jestem[j + 1]] / n) << endl;
					//cout << pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j + 1]] / n) << endl;
					gdzie_jestem[j]++;
				}
				if(gdzie_jestem[j] > l)
				{
					/*cout << i << " " << j << endl;
					for(auto x : miejsca)
					{
						cout << x.first << " " << x.second << endl;
					}
					for(auto x : per)
					{
						cout << x << " ";
					}*/
					cout << "-1" << endl;
					return 0;
				}
				temp.first = pref[j][gdzie_jestem[j]] - pref[j][gdzie_jestem[j] - 1] - ( pref[j][gdzie_jestem[j]] - pref[j][pop_calk] - nastepny(pop, war[j][gdzie_jestem[j] + 1]) - potrz[j]);
				temp.second = war[j][gdzie_jestem[j]];
				if(gdzie_jestem[j] < curmin)
				{
					curmin = gdzie_jestem[j];
					ktory = j;
					curminu = temp;
				}
				else if(gdzie_jestem[j] == curmin)
				{
					if(__int128(curminu.first) * __int128(temp.second) > __int128(temp.first) * __int128(curminu.second))
					{
						curminu = temp;
						ktory = j;
					}
				}
			}
		}
		pop_calk = curmin - 1;
		pop = curminu;
		czy_juz[ktory] = true;
		per.push_back(ktory);
		curminu.first += curminu.second * pop_calk;
		miejsca.push_back(curminu);
		for(__int128 j = 1; j <= n; j++)
		{
			gdzie_jestem[j] = curmin;
		}
	}
	for(__int128 i = 1; i <= n; i++)
	{
		if(!czy_juz[i])
		{
			per.push_back(i);
		}
	}
	for(auto x : miejsca)
	{
		cout << x.first << " " << x.second << endl;
	}
	for(auto x : per)
	{
		cout << x << " ";
	}
	cout << endl;
	return 0;
}

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