oj.uz

Submission #436193

# Submission time Handle Problem Language Result Execution time Memory
436193 2021-06-24T10:16:00 Z AmineTrabelsi Library (JOI18_library) C++14
19 / 100
 1053 ms 1044 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++){
		//cerr << i<<": \n";
		// insert book
		M[i-1] = 1;
		int q = Query(M);
		if(q > prev){
			//cerr << i<<": \n";
			curr.push_back({i}); // new group
			rem.push_back(0);
			prev = q;
		}else{
			cerr << i<<": "<<q<<"\n";
			// consider storing tables
			vector<int> side;
			for(int c=0;c<(int)curr.size();c++){
				if(rem[c])continue;
				cerr << c <<'\n';
				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);
			}
			
			for(auto s:side)cerr<<s<<" ";
				cerr<<'\n';
			// insert into first side
			vector<int> m(N);
			m[i-1] = 1;
			for(auto cc:curr[side[0]])m[cc-1] = 1;
				
				for(auto j:curr[side[0]]){
				cerr << j<<" ";
				
			}cerr<<'\n';
			bool pos = 0; // the insertion for next side
			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);
			}
			
			for(auto j:curr[side[0]]){
				cerr << j<<" ";
			}cerr<<'\n';
			
			// if theres another side merge
			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';
		}
	}
	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 198 ms 588 KB # of queries: 4635
2 Correct 199 ms 456 KB # of queries: 4835
3 Correct 207 ms 448 KB # of queries: 5106
4 Correct 220 ms 444 KB # of queries: 5241
5 Correct 239 ms 472 KB # of queries: 5130
6 Correct 207 ms 632 KB # of queries: 4995
7 Correct 234 ms 472 KB # of queries: 5144
8 Correct 180 ms 424 KB # of queries: 4563
9 Correct 220 ms 448 KB # of queries: 5329
10 Correct 87 ms 472 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 3 ms 200 KB # of queries: 56
16 Correct 6 ms 200 KB # of queries: 159

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 588 KB # of queries: 4635
2 Correct 199 ms 456 KB # of queries: 4835
3 Correct 207 ms 448 KB # of queries: 5106
4 Correct 220 ms 444 KB # of queries: 5241
5 Correct 239 ms 472 KB # of queries: 5130
6 Correct 207 ms 632 KB # of queries: 4995
7 Correct 234 ms 472 KB # of queries: 5144
8 Correct 180 ms 424 KB # of queries: 4563
9 Correct 220 ms 448 KB # of queries: 5329
10 Correct 87 ms 472 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 3 ms 200 KB # of queries: 56
16 Correct 6 ms 200 KB # of queries: 159
17 Runtime error 1053 ms 1044 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -