Submission #489832

#	Time	Username	Problem	Language	Result	Execution time	Memory
489832		Fran1024	Minerals (JOI19_minerals)	C++14	40 / 100	136 ms	6504 KiB

minerals

#include "minerals.h"
#include <vector>
#include <set>
#include <stdio.h>
using namespace std;

set <int> stroj;
int MCNT = 0;

void ubaciniz(vector <int> &v) {
	set <int> unizu;
	for(int i = 0; i < v.size(); i++) {
		unizu.insert(v[i]);
	}
	vector <int> pobrisani;
	for(auto it = stroj.begin(); it != stroj.end(); it++) {
		if(unizu.find(*it) == unizu.end()) {
			Query(*it);
			pobrisani.push_back(*it);
		}
	}
	for(int i = 0; i < pobrisani.size(); i++) {
		stroj.erase(pobrisani[i]);
	}
	for(int i = 0; i < v.size(); i++) {
		if(stroj.find(v[i]) == stroj.end()) {
			Query(v[i]);
			stroj.insert(v[i]);
		}
	}
}

int ubaci(int x) {
	if(stroj.find(x) == stroj.end()) {
		stroj.insert(x);
		return MCNT = Query(x);
	}
	return MCNT;
}

void izvadi(int x) {
	if(stroj.find(x) != stroj.end()) {
		stroj.erase(x);
		MCNT = Query(x);
	}
}

void divcon(vector <int> &a, vector <int> &b) {
	if(a.size() == 1) {
		Answer(a[0], b[0]);
		return;
	}
    /*printf("a.size() = %d, b.size() = %d\n", a.size(), b.size());*/
	vector <int> a1;
	vector <int> b1;
	vector <int> a2;
	vector <int> b2;
	for(int i = 0; i < a.size() / 2; i++) {
		a1.push_back(a[i]);
	}
	for(int i = a.size() / 2; i < a.size(); i++) {
		a2.push_back(a[i]);
	}
	ubaciniz(a1);
	for(int i = 0; i < b.size(); i++) {
		if(ubaci(b[i]) > a1.size()) {
			b2.push_back(b[i]);
		} else {
			b1.push_back(b[i]);
		}
		izvadi(b[i]);
	}
	divcon(a1, b1);
	divcon(a2, b2);
}

void Solve(int N) {
	 vector <int> a;
	 vector <int> b;
	 for(int i = 1; i <= 2 * N; i++) {
        int oldMCNT = MCNT;
	 	ubaci(i);
	 	if(MCNT == oldMCNT) {
	 		b.push_back(i);
		 } else {
		 	a.push_back(i);
		 }
	 }
	 //printf("a.size() = %d\n", a.size());
	 divcon(a, b);
}

Compilation message (stderr)

minerals.cpp: In function 'void ubaciniz(std::vector<int>&)':
minerals.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < pobrisani.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~
minerals.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < v.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp: In function 'void divcon(std::vector<int>&, std::vector<int>&)':
minerals.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < a.size() / 2; i++) {
      |                 ~~^~~~~~~~~~~~~~
minerals.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = a.size() / 2; i < a.size(); i++) {
      |                            ~~^~~~~~~~~~
minerals.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = 0; i < b.size(); i++) {
      |                 ~~^~~~~~~~~~
minerals.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if(ubaci(b[i]) > a1.size()) {
      |      ~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10