Submission #580181

#	Time	Username	Problem	Language	Result	Execution time	Memory
580181		penguinhacker	Art Collections (BOI22_art)	C++17	100 / 100	1748 ms	728 KiB

art

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

#define ll long long
#define ar array

void solve(int n) {
	vector<int> a(n), ans(n, -1);
	iota(a.begin(), a.end(), 1);
	int last=publish(a);
	for (int i=1; i<=n-1; ++i) {
		a.erase(a.begin());
		a.insert(a.begin()+n-i, i);
		int cur=publish(a);
		int bigger=(last-cur)+(n-i); // how many elements is p_i greater than {p_i+1, p_i+2, ... , p_n}
		assert(bigger%2==0);
		bigger/=2;
		for (int j=0; j<n; ++j) {
			if (ans[j]!=-1)
				continue;
			if (bigger==0) {
				ans[j]=i;
				break;
			}
			--bigger;
		}
		last=cur;
	}
	for (int i=0; i<n; ++i)
		if (ans[i]==-1)
			ans[i]=n;
	answer(ans);
}

Compilation message (stderr)

interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     if(v.size() != N) {
      |        ~~~~~~~~~^~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30