oj.uz

Submission #436199

# Submission time Handle Problem Language Result Execution time Memory
436199 2021-06-24T10:22:16 Z AmineTrabelsi Library (JOI18_library) C++14
19 / 100
 622 ms 488 KB 
#include <cstdio>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

void Solve(int N){
	vector<int> M(N);
	vector<int> res(N);
	vector<deque<int>> curr;
	vector<bool> rem;
	curr.push_back({1});
	rem.push_back(0);
	int prev = 1;
	M[0] = 1;
	for(int i=2;i<=N;i++){
		M[i-1] = 1;
		int q = Query(M);
		if(q > prev){
			curr.push_back({i});
			rem.push_back(0);
			prev = q;
		}else{
			vector<int> side;
			for(int c=0;c<(int)curr.size();c++){
				if(rem[c])continue;
				vector<int> m(N);
				m[i-1] = 1;
				for(auto cc:curr[c])m[cc-1] = 1;
				if(Query(m) == 1)side.push_back(c);
			}
			vector<int> m(N);
			m[i-1] = 1;
			for(auto cc:curr[side[0]])m[cc-1] = 1;
			bool pos = 0;
			if(curr[side[0]].size() > 1){
				m[curr[side[0]].back()-1] = 0;
				int q = Query(m);
				m[curr[side[0]].back()-1] = 1;
				if(q == 1){
					curr[side[0]].push_front(i);
				}else{
					pos = 1;
					curr[side[0]].push_back(i);
				}
			}else{
				curr[side[0]].push_front(i);
			}
			if((int)side.size() == 2){
				curr.push_back(deque<int>());
				rem.push_back(0);
				rem[side[1]] = 1;
				rem[side[0]] = 1;
				int c = curr[side[1]].front(),d = curr[side[1]].back();
				if(pos){
					m[c-1] = 1;
					q = Query(m);
					for(auto cc:curr[side[0]])curr.back().push_back(cc);
					if(q == 1){
						for(auto cc:curr[side[1]])curr.back().push_back(cc);
					}else 
						{
						reverse(curr[side[1]].begin(),curr[side[1]].end());
						for(auto cc:curr[side[1]])curr.back().push_back(cc);
						}
				}else{
					m[d-1] = 1;
					q = Query(m);
					if(q == 1){
						for(auto cc:curr[side[1]])curr.back().push_back(cc);
						for(auto cc:curr[side[0]])curr.back().push_back(cc);
					}else{
						reverse(curr[side[1]].begin(),curr[side[1]].end());
						for(auto cc:curr[side[1]])curr.back().push_back(cc);
						for(auto cc:curr[side[0]])curr.back().push_back(cc);
					}
				}
				prev--;
			}
		}
		/*
		for(int c=0;c<(int)curr.size();c++){
			if(!rem[c]){
			for(auto j:curr[c]){
				cerr << j<<" ";
			}
			cerr << '\n';
			}
		}
		cerr<<"out\n";*/
		
	}
	res = vector<int>(curr.back().begin(),curr.back().end());
	Answer(res);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 384 KB # of queries: 4635
2 Correct 91 ms 460 KB # of queries: 4835
3 Correct 119 ms 448 KB # of queries: 5106
4 Correct 119 ms 352 KB # of queries: 5241
5 Correct 92 ms 376 KB # of queries: 5130
6 Correct 86 ms 372 KB # of queries: 4995
7 Correct 57 ms 344 KB # of queries: 5144
8 Correct 51 ms 328 KB # of queries: 4563
9 Correct 109 ms 384 KB # of queries: 5329
10 Correct 50 ms 316 KB # of queries: 2210
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 1 ms 200 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 8
15 Correct 2 ms 200 KB # of queries: 56
16 Correct 3 ms 296 KB # of queries: 159

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 384 KB # of queries: 4635
2 Correct 91 ms 460 KB # of queries: 4835
3 Correct 119 ms 448 KB # of queries: 5106
4 Correct 119 ms 352 KB # of queries: 5241
5 Correct 92 ms 376 KB # of queries: 5130
6 Correct 86 ms 372 KB # of queries: 4995
7 Correct 57 ms 344 KB # of queries: 5144
8 Correct 51 ms 328 KB # of queries: 4563
9 Correct 109 ms 384 KB # of queries: 5329
10 Correct 50 ms 316 KB # of queries: 2210
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 2
13 Correct 1 ms 200 KB # of queries: 5
14 Correct 1 ms 200 KB # of queries: 8
15 Correct 2 ms 200 KB # of queries: 56
16 Correct 3 ms 296 KB # of queries: 159
17 Runtime error 622 ms 488 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -