Submission #757940

#	Time	Username	Problem	Language	Result	Execution time	Memory
757940		jer033	Fruits (NOI22_fruits)	C++17	5 / 100	237 ms	15048 KiB

Main

#include <algorithm>
#include <iostream>

int assigned[400005];
long long costs[400005];
long long answer[400005];
int available[400005];

using namespace std;

int main()
{
	int n;
	cin >> n;
	int subtwo=1;
	for (int i=1; i<=n; i++)
	{
		available[i]=1;
	}
	for (int i=1; i<=n; i++)
	{
		cin >> assigned[i];
		if (assigned[i]>0)
		{
			subtwo=0;
			available[assigned[i]]=0;
		}
	}
	if (subtwo)
	{
		answer[0]=0;
		for (int i=1; i<=n; i++)
		{
			cin >> costs[i];
			answer[i]=answer[i-1]+costs[i];
		}
		for (int i=0; i<n; i++)
		{
			cout << answer[n]-answer[n-1-i];
			if (i!=(n-1))
				cout << ' ';
			else
				cout << '\n';
		}
	}
	else
	{
		//let's assume subtask 5 holds
		int index=1;
		int curr=1;
		while (curr<=n)
		{
			if (assigned[index]>0)
			{
				curr=max(curr, assigned[index]);
			}
			else
			{
				while (available[curr]==0 and curr<=n)
					curr++;
				if (curr<=n)
				{
					assigned[index]=curr;
					curr++;
				}
			}
			index++;
		}
		//once curr=n+1 all remaining fruit assignments don't really matter anymore
		//you can keep them at -1, since they won't be bought by Benson anyways
		answer[0]=0;
		int max=0;
		for (int i=1; i<=n; i++)
		{
			answer[i]=answer[i-1];
			if (assigned[i]>max)
			{
				max=assigned[i];
				answer[i]++;
			}
		}
		for (int i=1; i<=n; i++)
		{
			cout << answer[i];
			if (i!=n)
				cout << ' ';
			else
				cout << '\n';
		}
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 13
• Subtask 5: 0 / 23
• Subtask 6: 0 / 42