Submission #1015071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015071		ByeWorld	Art Collections (BOI22_art)	C++17	100 / 100	1039 ms	1788 KiB

art

#include "art.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)/2)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int MAXA = 1e6+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
//
// --- Sample implementation for the task art ---
//
// To compile this program with the sample grader, place:
//     art.h art_sample.cpp sample_grader.cpp
// in a single folder, then open the terminal in this directory (right-click onto an empty spot in the directory,
// left click on "Open in terminal") and enter e.g.:
//     g++ -std=c++17 art_sample.cpp sample_grader.cpp
// in this folder. This will create a file a.out in the current directory which you can execute from the terminal
// as ./a.out
// See task statement or sample_grader.cpp for the input specification
//

int n;
vector <int> vec;
pii que(int x){
	vector <int> te;
	for(int i=1; i<=n; i++)
		if(i!=x) te.pb(i);
	te.pb(x);
	int a = publish(te);
	te.clear();
	te.pb(x);
	for(int i=1; i<=n; i++)
		if(i!=x) te.pb(i);
	int b = publish(te);
	return {a, b};
}
// 1...n-1 n --> p + x
// n 1...n-1  --> p + (n-1)-x
int Q(int x){
	vector <int> te;
	te.pb(x);
	for(int i=1; i<=n; i++)
		if(i!=x) te.pb(i);
	return publish(te);
}
void solve(int N) {
	n = N;
	vec.resize(n);
	pii te = que(n); te.se -= (n-1);
	int las = (te.fi+te.se)/2; // (1 2..) n-1   --> p
	vec[n-1-(te.fi-te.se)/2] = n; // 1.n 2.n ... n-1.n --> inverse brp
	int sum = (te.fi-te.se)/2;
	// cout << sum << " sum\n";

	for(int i=n-1; i>=2; i--){
		int te = Q(i); // n-1 (1 2 ... n-2) n
		// las --> (1 2..) n-1 --> p+x
		te -= sum; // n-1 (1 2 ... n-2) --> p +n-2 -x
		te -= i-1; // p - x

		int idx = (las-te)/2; // ngitung (1 2 .. n-2) inverse
		int nw = n-1, cnt = 0; 
		for(; nw>=0; nw--){
			if(vec[nw]==0) cnt++;
			if(cnt==idx+1) break;
		}
		// cout << idx << " " << i << ' ' << nw<<" pp\n";
		vec[nw] = i;
		las = (las+te)/2;
		sum += idx;
	}
	for(int i=0; i<n; i++)
		if(vec[i]==0) vec[i] = 1;
    answer(vec);
}
/*
g++ -static -DEVAL -o a sample_grader.cpp art_sample.cpp
*/

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