Submission #724131

#	Time	Username	Problem	Language	Result	Execution time	Memory
724131		WonderfulWhale	Art Collections (BOI22_art)	C++17	100 / 100	1598 ms	796 KiB

art

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

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

struct V {
	V *next = nullptr;
	int num = 0;
	V(V *next, int num) : next(next), num(num) {}
};

void solve(int n) {
	vector<int> query;
	for(int i=1;i<=n;i++) query.pb(i);
	V* tail = new V(nullptr, n);
	int X = publish(query);
	for(int i=n-1;i;i--) {
		V* tmp = tail;
		int cnt=0;
		while(tmp->num!=n) {
			cnt++;
			tmp=tmp->next;
		}
		int correction = -cnt + ((n-i-1)-cnt);
		swap(query[i-1], query[n-1]);
		int x = publish(query)+correction;
		int b = (n-i-(X-x))/2;
		int a = (n-i)-b;
		V* cur = tail;
		if(a==0) {
			tail = new V(tail, i);
		} else {
			for(int j=0;j<a-1;j++) {
				cur = cur->next;
			}
			cur->next = new V(cur->next, i);
		}
		swap(query[i-1], query[n-1]);
	}
	vector<int> ans;
	while(tail) {
		ans.pb(tail->num);
		tail = tail->next;
	}
	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