Submission #1220990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220990		ssafarov	Library (JOI18_library)	C++20	Compilation error	0 ms	0 KiB

library

vector<int> nw(vector<int> v, int x){
	vector<int> nv;
	for(auto g :v){
		if(g == x) continue;
		nv.push_back(g);
	}
	return nv;
}

void Solve(int n)
{
	mt19937 rng(time(0));
	deque<int> dq;
	dq.push_back(1);
	if(n == 1){
		vector<int> ans;
		ans.push_back(1);
		Answer(ans);
		return;
	}
	vector<int> v;
	for(int i = 2; i <= n; ++i) v.push_back(i);
	shuffle(v.begin(), v.end(), rng);
	int l = -1;
	int r = n - 1;
	while(r - l > 1){
		int mid = (l + r) / 2;
		vector<int> nv(n);
		vector<int> nv2(n);
		for(auto g : dq){
			nv[g - 1] = 1;
			if(g != 1) nv2[g - 1] = 1;
		}
		for(int i = 0; i <= mid; ++i){
			nv[v[i] - 1] = 1;
			nv2[v[i] - 1] = 1;
		}
		int cnt = Query(nv);
		int nc = Query(nv2);
		if(nc == (cnt - 1)){
			l = mid;
		}else r = mid;
	}
	dq.push_back(v[r]);
	v = nw(v, v[r]);
	int ct = 0;
	for(int i = 3; i <= n; ++i){
		int l = -1;
		int r = n - i + 1;
		while(r - l > 1){
			int mid = (l + r) / 2;
			vector<int> sv(n);
			vector<int> nv1(n);
			vector<int> nv2(n);
			for(auto g : dq){
				sv[g - 1] = 1;
				if(g != dq.front())nv1[g - 1] = 1;
				if(g != dq.back()) nv2[g - 1] = 1;
			}
			for(int i = 0; i <= mid; ++i){
				sv[v[i] - 1] = 1;
				nv1[v[i] - 1] = 1;
				nv2[v[i] - 1] = 1;
			}
			int rct = Query(sv);
			if(ct == 0){
				int cnt = Query(nv1);
				if(rct == cnt){
					l = mid;
				}else{
					r = mid;
				}
			}else{
				int cnt = Query(nv2);
				if(rct == cnt){
					l = mid;
				}else{
					r = mid;
				}
			}
		}
		vector<int> sv(n);
		vector<int> nv1(n);
		vector<int> nv2(n);
		for(auto g : dq){
			sv[g - 1] = 1;
			if(g != dq.front())nv1[g - 1] = 1;
			if(g != dq.back()) nv2[g - 1] = 1;
		}
		for(int i = 0; i <= r; ++i){
			sv[v[i] - 1] = 1;
			nv1[v[i] - 1] = 1;
			nv2[v[i] - 1] = 1;
		}
		int rct = Query(sv);
		if(ct == 0){
			int cnt = Query(nv1);
			if(cnt == rct){
				ct = 1;
				i--;
				continue;
			}
		}
		if(ct == 0){
			dq.push_front(v[r]);
		}else{
			dq.push_back(v[r]);
		}
		v = nw(v, v[r]);
	}
	vector<int> ans;
	for(auto g : dq){
		ans.push_back(g);
	}
	Answer(ans);
}

Compilation message (stderr)

library.cpp:1:1: error: 'vector' does not name a type
    1 | vector<int> nw(vector<int> v, int x){
      | ^~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:12:9: error: 'mt19937' was not declared in this scope
   12 |         mt19937 rng(time(0));
      |         ^~~~~~~
library.cpp:13:9: error: 'deque' was not declared in this scope
   13 |         deque<int> dq;
      |         ^~~~~
library.cpp:13:15: error: expected primary-expression before 'int'
   13 |         deque<int> dq;
      |               ^~~
library.cpp:14:9: error: 'dq' was not declared in this scope
   14 |         dq.push_back(1);
      |         ^~
library.cpp:16:17: error: 'vector' was not declared in this scope
   16 |                 vector<int> ans;
      |                 ^~~~~~
library.cpp:16:24: error: expected primary-expression before 'int'
   16 |                 vector<int> ans;
      |                        ^~~
library.cpp:17:17: error: 'ans' was not declared in this scope
   17 |                 ans.push_back(1);
      |                 ^~~
library.cpp:18:17: error: 'Answer' was not declared in this scope
   18 |                 Answer(ans);
      |                 ^~~~~~
library.cpp:21:9: error: 'vector' was not declared in this scope
   21 |         vector<int> v;
      |         ^~~~~~
library.cpp:21:16: error: expected primary-expression before 'int'
   21 |         vector<int> v;
      |                ^~~
library.cpp:22:37: error: 'v' was not declared in this scope
   22 |         for(int i = 2; i <= n; ++i) v.push_back(i);
      |                                     ^
library.cpp:23:17: error: 'v' was not declared in this scope
   23 |         shuffle(v.begin(), v.end(), rng);
      |                 ^
library.cpp:23:37: error: 'rng' was not declared in this scope
   23 |         shuffle(v.begin(), v.end(), rng);
      |                                     ^~~
library.cpp:23:9: error: 'shuffle' was not declared in this scope
   23 |         shuffle(v.begin(), v.end(), rng);
      |         ^~~~~~~
library.cpp:28:24: error: expected primary-expression before 'int'
   28 |                 vector<int> nv(n);
      |                        ^~~
library.cpp:29:24: error: expected primary-expression before 'int'
   29 |                 vector<int> nv2(n);
      |                        ^~~
library.cpp:31:25: error: 'nv' was not declared in this scope; did you mean 'n'?
   31 |                         nv[g - 1] = 1;
      |                         ^~
      |                         n
library.cpp:32:36: error: 'nv2' was not declared in this scope
   32 |                         if(g != 1) nv2[g - 1] = 1;
      |                                    ^~~
library.cpp:35:25: error: 'nv' was not declared in this scope; did you mean 'n'?
   35 |                         nv[v[i] - 1] = 1;
      |                         ^~
      |                         n
library.cpp:36:25: error: 'nv2' was not declared in this scope
   36 |                         nv2[v[i] - 1] = 1;
      |                         ^~~
library.cpp:38:33: error: 'nv' was not declared in this scope; did you mean 'n'?
   38 |                 int cnt = Query(nv);
      |                                 ^~
      |                                 n
library.cpp:38:27: error: 'Query' was not declared in this scope
   38 |                 int cnt = Query(nv);
      |                           ^~~~~
library.cpp:39:32: error: 'nv2' was not declared in this scope
   39 |                 int nc = Query(nv2);
      |                                ^~~
library.cpp:45:13: error: 'nw' was not declared in this scope; did you mean 'n'?
   45 |         v = nw(v, v[r]);
      |             ^~
      |             n
library.cpp:52:32: error: expected primary-expression before 'int'
   52 |                         vector<int> sv(n);
      |                                ^~~
library.cpp:53:32: error: expected primary-expression before 'int'
   53 |                         vector<int> nv1(n);
      |                                ^~~
library.cpp:54:32: error: expected primary-expression before 'int'
   54 |                         vector<int> nv2(n);
      |                                ^~~
library.cpp:56:33: error: 'sv' was not declared in this scope
   56 |                                 sv[g - 1] = 1;
      |                                 ^~
library.cpp:57:52: error: 'nv1' was not declared in this scope
   57 |                                 if(g != dq.front())nv1[g - 1] = 1;
      |                                                    ^~~
library.cpp:58:52: error: 'nv2' was not declared in this scope
   58 |                                 if(g != dq.back()) nv2[g - 1] = 1;
      |                                                    ^~~
library.cpp:61:33: error: 'sv' was not declared in this scope
   61 |                                 sv[v[i] - 1] = 1;
      |                                 ^~
library.cpp:62:33: error: 'nv1' was not declared in this scope
   62 |                                 nv1[v[i] - 1] = 1;
      |                                 ^~~
library.cpp:63:33: error: 'nv2' was not declared in this scope
   63 |                                 nv2[v[i] - 1] = 1;
      |                                 ^~~
library.cpp:65:41: error: 'sv' was not declared in this scope
   65 |                         int rct = Query(sv);
      |                                         ^~
library.cpp:65:35: error: 'Query' was not declared in this scope
   65 |                         int rct = Query(sv);
      |                                   ^~~~~
library.cpp:67:49: error: 'nv1' was not declared in this scope
   67 |                                 int cnt = Query(nv1);
      |                                                 ^~~
library.cpp:74:49: error: 'nv2' was not declared in this scope
   74 |                                 int cnt = Query(nv2);
      |                                                 ^~~
library.cpp:82:24: error: expected primary-expression before 'int'
   82 |                 vector<int> sv(n);
      |                        ^~~
library.cpp:83:24: error: expected primary-expression before 'int'
   83 |                 vector<int> nv1(n);
      |                        ^~~
library.cpp:84:24: error: expected primary-expression before 'int'
   84 |                 vector<int> nv2(n);
      |                        ^~~
library.cpp:86:25: error: 'sv' was not declared in this scope
   86 |                         sv[g - 1] = 1;
      |                         ^~
library.cpp:87:44: error: 'nv1' was not declared in this scope
   87 |                         if(g != dq.front())nv1[g - 1] = 1;
      |                                            ^~~
library.cpp:88:44: error: 'nv2' was not declared in this scope
   88 |                         if(g != dq.back()) nv2[g - 1] = 1;
      |                                            ^~~
library.cpp:91:25: error: 'sv' was not declared in this scope
   91 |                         sv[v[i] - 1] = 1;
      |                         ^~
library.cpp:92:25: error: 'nv1' was not declared in this scope
   92 |                         nv1[v[i] - 1] = 1;
      |                         ^~~
library.cpp:93:25: error: 'nv2' was not declared in this scope
   93 |                         nv2[v[i] - 1] = 1;
      |                         ^~~
library.cpp:95:33: error: 'sv' was not declared in this scope
   95 |                 int rct = Query(sv);
      |                                 ^~
library.cpp:95:27: error: 'Query' was not declared in this scope
   95 |                 int rct = Query(sv);
      |                           ^~~~~
library.cpp:97:41: error: 'nv1' was not declared in this scope
   97 |                         int cnt = Query(nv1);
      |                                         ^~~
library.cpp:111:16: error: expected primary-expression before 'int'
  111 |         vector<int> ans;
      |                ^~~
library.cpp:113:17: error: 'ans' was not declared in this scope
  113 |                 ans.push_back(g);
      |                 ^~~
library.cpp:115:16: error: 'ans' was not declared in this scope
  115 |         Answer(ans);
      |                ^~~
library.cpp:115:9: error: 'Answer' was not declared in this scope
  115 |         Answer(ans);
      |         ^~~~~~