Submission #573077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
573077	2022-06-05T17:40:04 Z	StrawHatWess	Art Collections (BOI22_art)	C++17	20 / 100	129 ms	576 KB

#include "art.h"

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

typedef vector<int>vi; 
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define FOR(i,a,b) for(int i=a; i<b; i++)


mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int random(int a, int b){
    return a + rng() % (b - a + 1);
}

//------------------------------

const int MX=1e5; 

int N;

vi solve(vi vec){
	//for(int x: vec) cout << x << " "; cout << endl;

	int n=sz(vec); 
	if(n<=1) return vec; 

	int i=random(0,n-1); 
	int pi=vec[0]; 
	

	map<int,int>mp;
	vi q={pi};
	FOR(i,0,n) if(vec[i]!=pi) q.pb(vec[i]),mp[vec[i]]=1; 

	FOR(i,1,N+1) if(!mp.count(i) && i!=pi) q.pb(i); 

	int x=publish(q); 
	//cout << x << endl;


	//for(int x: q) cout << x << " "; cout << endl;


	vi l,r; 
	FOR(i,0,n-1){
		//if(i+1>=N) break; 
		assert(q[i]==pi); 
		swap(q[i],q[i+1]);

		int y=publish(q);
		//cout << y << endl;

		if(y>x) r.pb(q[i]); 
		else l.pb(q[i]); 

		x=y; 
	}

	/*for(int x: l) cout << x << " "; cout << endl;
	for(int x: r) cout << x << " "; cout << endl;*/

	l=solve(l); 
	r=solve(r); 

	vi ans=l; 
	ans.pb(pi); 
	for(int x: r) ans.pb(x); 

	//for(int x: ans) cout << x << " "; cout << endl;

	return ans; 
}

void solve(int N){
	::N=N; 
	vi vec(N); iota(all(vec),1);  
	vec=solve(vec);
	answer(vec); 
}

Compilation message

art.cpp: In function 'vi solve(vi)':
art.cpp:31:6: warning: unused variable 'i' [-Wunused-variable]
   31 |  int i=random(0,n-1);
      |      ^
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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	3 ms	208 KB	Output is correct
10	Correct	3 ms	208 KB	Output is correct
11	Correct	3 ms	304 KB	Output is correct
12	Correct	4 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	208 KB	Output is correct
16	Correct	1 ms	208 KB	Output is correct
17	Correct	1 ms	208 KB	Output is correct
18	Correct	1 ms	208 KB	Output is correct
19	Correct	13 ms	324 KB	Output is correct
20	Correct	15 ms	348 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	3 ms	208 KB	Output is correct
10	Correct	3 ms	208 KB	Output is correct
11	Correct	3 ms	304 KB	Output is correct
12	Correct	4 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	208 KB	Output is correct
16	Correct	1 ms	208 KB	Output is correct
17	Correct	1 ms	208 KB	Output is correct
18	Correct	1 ms	208 KB	Output is correct
19	Correct	13 ms	324 KB	Output is correct
20	Correct	15 ms	348 KB	Output is correct
21	Correct	1 ms	208 KB	Output is correct
22	Correct	4 ms	208 KB	Output is correct
23	Correct	4 ms	312 KB	Output is correct
24	Correct	4 ms	312 KB	Output is correct
25	Correct	4 ms	248 KB	Output is correct
26	Incorrect	129 ms	576 KB	Not correct
27	Halted	0 ms	0 KB	-

Subtask #4
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	3 ms	208 KB	Output is correct
10	Correct	3 ms	208 KB	Output is correct
11	Correct	3 ms	304 KB	Output is correct
12	Correct	4 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	208 KB	Output is correct
16	Correct	1 ms	208 KB	Output is correct
17	Correct	1 ms	208 KB	Output is correct
18	Correct	1 ms	208 KB	Output is correct
19	Correct	13 ms	324 KB	Output is correct
20	Correct	15 ms	348 KB	Output is correct
21	Correct	1 ms	208 KB	Output is correct
22	Correct	4 ms	208 KB	Output is correct
23	Correct	4 ms	312 KB	Output is correct
24	Correct	4 ms	312 KB	Output is correct
25	Correct	4 ms	248 KB	Output is correct
26	Incorrect	129 ms	576 KB	Not correct
27	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	3 ms	208 KB	Output is correct
10	Correct	3 ms	208 KB	Output is correct
11	Correct	3 ms	304 KB	Output is correct
12	Correct	4 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	208 KB	Output is correct
16	Correct	1 ms	208 KB	Output is correct
17	Correct	1 ms	208 KB	Output is correct
18	Correct	1 ms	208 KB	Output is correct
19	Correct	13 ms	324 KB	Output is correct
20	Correct	15 ms	348 KB	Output is correct
21	Correct	1 ms	208 KB	Output is correct
22	Correct	4 ms	208 KB	Output is correct
23	Correct	4 ms	312 KB	Output is correct
24	Correct	4 ms	312 KB	Output is correct
25	Correct	4 ms	248 KB	Output is correct
26	Incorrect	129 ms	576 KB	Not correct
27	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	208 KB	Output is correct
6	Correct	1 ms	208 KB	Output is correct
7	Correct	1 ms	208 KB	Output is correct
8	Correct	1 ms	208 KB	Output is correct
9	Correct	3 ms	208 KB	Output is correct
10	Correct	3 ms	208 KB	Output is correct
11	Correct	3 ms	304 KB	Output is correct
12	Correct	4 ms	208 KB	Output is correct
13	Correct	1 ms	208 KB	Output is correct
14	Correct	0 ms	208 KB	Output is correct
15	Correct	1 ms	208 KB	Output is correct
16	Correct	1 ms	208 KB	Output is correct
17	Correct	1 ms	208 KB	Output is correct
18	Correct	1 ms	208 KB	Output is correct
19	Correct	13 ms	324 KB	Output is correct
20	Correct	15 ms	348 KB	Output is correct
21	Correct	1 ms	208 KB	Output is correct
22	Correct	4 ms	208 KB	Output is correct
23	Correct	4 ms	312 KB	Output is correct
24	Correct	4 ms	312 KB	Output is correct
25	Correct	4 ms	248 KB	Output is correct
26	Incorrect	129 ms	576 KB	Not correct
27	Halted	0 ms	0 KB	-

Submission #573077

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 0 / 15.0

Subtask #4 0 / 15.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
0 / 15.0

Subtask #4
0 / 15.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0