oj.uz

Submission #582181

# Submission time Handle Problem Language Result Execution time Memory
582181 2022-06-23T13:34:43 Z almothana05 Library (JOI18_library) C++14
19 / 100
 542 ms 3252 KB 
#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
   using namespace std;
void Solve(int menge){
   vector<int>num , erge;
   set<int>comp;
   deque<int> ed[2000];
	
	int erg , cmp , numm , nummer;
	vector<int> M(menge, 0);
	for(int i = 0 ; i < menge ; i++){
		M[i] = 0;
	}

	for(int i = 0 ; i < menge ;i++){
		num.push_back(i + 1);
	}

	for(int i = 1; i <= menge ; i++){	
		ed[i].push_back(i);
	}

	int st , en , mit;
	erg = 1;
	// cout << "ja\n";
	for(int i = 2 ; i <= menge ; i++){
		// cout << i << ' ';
		for(int j = 1 ; j <= i ;j++){
			M[j - 1] = 1;
		}
		// for(int j = 0 ; j < M.size() ; j++){
		// 	cout << M[j] << " ";
		// }
		// cout << "\n";
		numm = Query(M);
		for(int j = 1 ; j <= i ;j++){
			M[j] = 0;
		}
		// cout << erg << ' ' << numm << "\n";
		if(numm == erg){
			// cout << "eins\n";
			st = 1; en = i - 1;
			while(st <= en){
				mit = (st + en)/2;
				// cout << mit << ' ';
				for(int j = 0 ; j < menge ; j++){
					if(num[j] <= mit){
						M[j] = 1;
						comp.insert(num[j]);
					}
				}
				M[i - 1] = 1;
				// for(int j = 0 ; j < menge ; j++){
					// cout << M[j] << ' ';
				// }
				// cout << "\n";
				nummer = Query(M);
				// cout << numm << "\n";
				for(int j = 0 ; j < menge ; j++){
					M[j] = 0;
				}

				if(nummer == comp.size()){
					// cout << "en\n";
					en = mit - 1;
				}
				else{
					st = mit + 1;
					// cout << "st\n";
				}
				comp.clear();
			}
			// cout << st << "\n";
			// cout << ed[st].size() << "\n";
			num[i - 1] = st;
			M[i - 1] = 1;
			M[ed[st].front() - 1] = 1;
			if(Query(M) == 1){
				ed[st].push_front(i);
			}
			else{
				ed[st].push_back(i);
			}
			M[i - 1] = 0;
			M[ed[st].front() - 1] = 0;
		}
		else if(numm < erg){
			// cout << "zwei\n";
			int er ,zw;
			st = 1; en = i - 1;
			while(st <= en){
				mit = (st + en)/2;
				for(int j = 0 ; j < menge ; j++){
					if(num[j] <= mit){
						M[j] = 1;
						comp.insert(num[j]);
					}
				}
				M[i - 1] = 1;
				nummer = Query(M);
				
				for(int j = 0 ; j < menge ; j++){
					M[j] = 0;
				}

				if(nummer <= comp.size()){
					en = mit - 1;
				}
				else{
					st = mit + 1;
				}
				comp.clear();
			}
			er = st;
			M[i - 1] = 1;
			M[ed[st].front() - 1] = 1;
			if(Query(M) == 1){
				ed[st].push_front(i) ;
			}
			else{
				ed[st].push_back(i) ;
			}
			M[i - 1] = 0;
			M[ed[st].front() - 1] = 0;



			st = 1; en = i - 1;
			while(st <= en){
				mit = (st + en)/2;
				// cout << mit << "\n";
				for(int j = 0 ; j < menge ; j++){
					if(num[j] <= mit){
						M[j] = 1;
						comp.insert(num[j]);
					}
				}
				M[i - 1] = 1;
				
				nummer = Query(M);
				for(int j = 0 ; j < menge ; j++){
					M[j] = 0;
				}

				if(nummer < comp.size()){
					en = mit - 1;
				}
				else{
					st = mit + 1;
				}
				comp.clear();
			}
			zw = st;
			// cout << er << ' ' << zw << "\n";
			M[i - 1] = 1;
			M[ed[st].front() - 1] = 1;
			if(Query(M) == 1){
				ed[st].push_front(i);
			}
			else{
				ed[st].push_back(i);
			}
			M[i - 1] = 0;
			M[ed[st].front() - 1] = 0;

			if(ed[er].front() == ed[zw].back()){
				ed[er].pop_front();
				while(ed[zw].size()){
					num[ed[zw].back() - 1] = er;
					ed[er].push_front(ed[zw].back());
					ed[zw].pop_back();
				}
			}
			else if(ed[er].front() == ed[zw].front()){
				ed[er].pop_front();
				while(ed[zw].size()){
					num[ed[zw].front() - 1] = er;
					ed[er].push_front(ed[zw].front());
					ed[zw].pop_front();
				}
			}
			else if(ed[er].back() == ed[zw].front()){
				ed[er].pop_back();
				while(ed[zw].size()){
					num[ed[zw].front() - 1] = er;
					ed[er].push_back(ed[zw].front());
					ed[zw].pop_front();
				}
			}
			else{
				ed[er].pop_back();
				while(ed[zw].size()){
					num[ed[zw].back() - 1] = er;
					ed[er].push_back(ed[zw].back());
					ed[zw].pop_back();
				}
			}
			
		}
		erg = numm;
		// for(int i = 0 ; i < num.size() ; i++){
		// 	cout << num[i] << ' '; 
		// }
		// cout << "\n";
	}
	while(ed[num[0]].size()){
		// cout << ed[num[0]].front() << "\n";
		erge.push_back(ed[num[0]].front());
		ed[num[0]].pop_front();
	}
	
	Answer(erge);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     if(nummer == comp.size()){
      |        ~~~~~~~^~~~~~~~~~~~~~
library.cpp:108:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     if(nummer <= comp.size()){
      |        ~~~~~~~^~~~~~~~~~~~~~
library.cpp:147:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     if(nummer < comp.size()){
      |        ~~~~~~~^~~~~~~~~~~~~
library.cpp:11:12: warning: unused variable 'cmp' [-Wunused-variable]
   11 |  int erg , cmp , numm , nummer;
      |            ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1656 KB # of queries: 1707
2 Correct 22 ms 1616 KB # of queries: 1693
3 Correct 35 ms 1656 KB # of queries: 1788
4 Correct 38 ms 1616 KB # of queries: 1769
5 Correct 33 ms 1616 KB # of queries: 1798
6 Correct 37 ms 1644 KB # of queries: 1777
7 Correct 46 ms 1616 KB # of queries: 1780
8 Correct 32 ms 1644 KB # of queries: 1703
9 Correct 35 ms 1648 KB # of queries: 1785
10 Correct 16 ms 1616 KB # of queries: 1068
11 Correct 1 ms 1616 KB # of queries: 0
12 Correct 1 ms 1616 KB # of queries: 3
13 Correct 2 ms 1616 KB # of queries: 6
14 Correct 1 ms 1616 KB # of queries: 11
15 Correct 2 ms 1616 KB # of queries: 74
16 Correct 5 ms 1616 KB # of queries: 155

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1656 KB # of queries: 1707
2 Correct 22 ms 1616 KB # of queries: 1693
3 Correct 35 ms 1656 KB # of queries: 1788
4 Correct 38 ms 1616 KB # of queries: 1769
5 Correct 33 ms 1616 KB # of queries: 1798
6 Correct 37 ms 1644 KB # of queries: 1777
7 Correct 46 ms 1616 KB # of queries: 1780
8 Correct 32 ms 1644 KB # of queries: 1703
9 Correct 35 ms 1648 KB # of queries: 1785
10 Correct 16 ms 1616 KB # of queries: 1068
11 Correct 1 ms 1616 KB # of queries: 0
12 Correct 1 ms 1616 KB # of queries: 3
13 Correct 2 ms 1616 KB # of queries: 6
14 Correct 1 ms 1616 KB # of queries: 11
15 Correct 2 ms 1616 KB # of queries: 74
16 Correct 5 ms 1616 KB # of queries: 155
17 Correct 516 ms 1952 KB # of queries: 11271
18 Correct 475 ms 1824 KB # of queries: 11158
19 Correct 542 ms 1708 KB # of queries: 11275
20 Runtime error 399 ms 3252 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -