Submission #582219

#	Time	Username	Problem	Language	Result	Execution time	Memory
582219		almothana05	Library (JOI18_library)	C++17	19 / 100	392 ms	3372 KiB

library

#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];
	
	vector<int> M(menge, 0);
	int erg , cmp , numm , nummer;
	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;
         while(ed[st].size() > 0);;
			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;
         while(ed[st].size() > 0);;
			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;
         while(ed[st].size() > 0);;
			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 (stderr)

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:109:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     if(nummer <= comp.size()){
      |        ~~~~~~~^~~~~~~~~~~~~~
library.cpp:149:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     if(nummer < comp.size()){
      |        ~~~~~~~^~~~~~~~~~~~~
library.cpp:12:12: warning: unused variable 'cmp' [-Wunused-variable]
   12 |  int erg , cmp , numm , nummer;
      |            ^~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 81