Kirjat

input/code.cpp: In function 'int main()':
input/code.cpp:98:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (indx != used.size() && suitable <= n) {
               ^
input/code.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < repair.size(); i++) {
                    ^
input/code.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (indx != used.size() && curSuitable <= n) {
               ^
input/code.cpp:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < used.size(); i++) {
                      ^

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <sstream>
 
int binarySearch(std::vector<std::pair<int, int>>& sorted, int searchedFor);
int binarySearch(std::vector<std::pair<int, int>>& sorted, std::pair<int, int> p);
void sortAlmostSorted(std::vector<std::pair<int, int>>&);
 
int main() {
	
	std::ios_base::sync_with_stdio(false);
 
	int n = 0;
	std::string nS;
	std::string f;
	std::string s;
 
	getline(std::cin, nS);
	getline(std::cin, f);
	getline(std::cin, s);
 
	n = (int)stof(nS);
 
	std::vector<int> first;
	std::vector<int> second;
 
	std::stringstream ss(f);
	std::stringstream ss2(s);
 
	std::string cur;
 
	for (int i = 0; i < n; i++) {
		ss >> cur;
		first.push_back((int)stof(cur));
		ss2 >> cur;
		second.push_back((int)stof(cur));
	}
 
	n = (int)stof(nS);
	int curF;
	int curS;
 
	std::string result;
 
	std::map<int, std::vector<int>> indices;
	std::map<int, std::vector<int>>::iterator itr;
 
	std::vector<std::pair<int, int>> nums;
	nums.reserve(n);
 
	std::vector<std::pair<int, int>> used;
	int indx = 0;
	std::pair<int, int>* currentPair;
	int current = 0;
 
	used.reserve(n);
	
	std::vector<std::pair<int, int>> repair;
	int suitable = 0;
 
	for (int i = 0; i < n; i++) {
 
		curF = first.at(i);
		curS = second.at(i);
 
		itr = indices.find(curF);
 
		nums.push_back(std::pair<int, int>(curF, curS));
 
		if (itr != indices.end()) {
			itr->second.push_back((int)(i));
		}
		else {
			indices.insert(std::pair<int, std::vector<int>>(curF, std::vector<int>(1, i)));
 
		}
 
		itr = indices.find(curS);
 
		if (itr != indices.end()) {
			itr->second.push_back(i);
 
		}
		else {
			indices.insert(std::pair<int, std::vector<int>>(curS, std::vector<int>(1, i)));
 
		}
 
		
		suitable = (curF * curF + abs(curS - curF)) % n + 1;
		indx = binarySearch(used, suitable);
 
		while (indx != used.size() && suitable <= n) {
			currentPair = &used.at(indx);
			current = currentPair->second;
			suitable = abs((curF * curF * (current * current) + abs(curS - curF)) % n + 1);
			currentPair->second++;
 
			indx = binarySearch(used, suitable);
		}
 
		if (suitable <= 0 || suitable == curF || suitable == curS) {
			repair.push_back(std::pair<int, int>(result.size(), i));
		}
		else {
			used.push_back(std::pair<int, int>(suitable, 1));
			sortAlmostSorted(used);
		}
 
		result.append(std::to_string(suitable));
		result.append(" ");
	}
 
	int curSuitable = 0;
	int curInd = 0;
	int num1 = 0;
	int num2 = 0;
 
	for (int i = 0; i < repair.size(); i++) {
		curSuitable = 1;
		indx = binarySearch(used, curSuitable);
 
		while (indx != used.size() && curSuitable <= n) {
			curSuitable++;
			indx = binarySearch(used, curSuitable);
		}
		
		used.push_back(std::pair<int, int>(curSuitable, 1));
		curInd = repair.at(i).second;
 
		num1 = indices.at(curSuitable).at(0);
		num2 = indices.at(curSuitable).at(1);
 
		int curUsed = 0;
		int j = 0;
 
		if (num1 == curInd || num2 == curInd) {
			for (int i = 0; i < used.size(); i++) {
				curUsed = used.at(i).first;
 
				if (curSuitable != curUsed && curUsed != num1 && curUsed != num2 
					&& nums.at(j).first != curSuitable && nums.at(j).second != curSuitable) {
					int index = result.find(" " + std::to_string(curUsed) + " ");
					result.replace(index+1, std::to_string(curUsed).length(), std::to_string(curSuitable));
					curSuitable = curUsed;
					break;
				}
				j++;
			}
		}
 
		result.replace(repair.at(i).first, 1, std::to_string(curSuitable));
	}
 
	std::cout << result;
 
	//POISTA MY�HEMMIN
	getchar();
 
	return 0;
}
 
int binarySearch(std::vector<std::pair<int, int>>& sorted, int searchedFor) {
	int i = 0;
	int length = sorted.size();
 
	if (length <= 0) {
		return false;
	}
 
	for (int n = length / 2; n >= 1; n /= 2) {
		while (i + n < length && sorted.at(i + n).first <= searchedFor) {
			i += n;
		}
	}
	
	if (sorted.at(i).first == searchedFor) {
		return i;
	}
 
	return sorted.size();
}
 
int binarySearch(std::vector<std::pair<int, int>>& sorted, std::pair<int, int> p) {
	int i = 0;
	int length = sorted.size();
	int searchedFor = p.first;
 
	if (length <= 0) {
		return false;
	}
 
	for (int n = length / 2; n >= 1; n /= 2) {
		while (i + n < length && sorted.at(i + n).first <= searchedFor) {
			i += n;
		}
	}
 
	return i;
}
 
void sortAlmostSorted(std::vector<std::pair<int, int>>& almostSorted) {
	int l = almostSorted.size();
 
	if (l <= 1) {
		return;
	}
 
	int last = almostSorted.at(l - 2).first;
	std::pair<int, int> inserted = almostSorted.at(l - 1);
 
	if (inserted.first >= last) {
		return;
	}
	else if (inserted.first <= almostSorted.at(0).first) {
		almostSorted.insert(almostSorted.begin(), inserted);
	}
 
	almostSorted.pop_back();
 
	int index = binarySearch(almostSorted, inserted);
	int number = almostSorted.at(index).first;
 
	if (number > inserted.first) {
		almostSorted.insert(almostSorted.begin() + index - 1, inserted);
	}
	else {
		almostSorted.insert(almostSorted.begin() + index + 1, inserted);
	}
 
}
 
 

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: WRONG ANSWER

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: WRONG ANSWER

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: WRONG ANSWER

Test 15

Group: 1

Verdict: WRONG ANSWER

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: WRONG ANSWER

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: WRONG ANSWER

Test 22

Group: 2

Verdict: WRONG ANSWER

Test 23

Group: 2

Verdict: WRONG ANSWER

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: WRONG ANSWER

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: WRONG ANSWER

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 2

Verdict: WRONG ANSWER

Test 33

Group: 2

Verdict: WRONG ANSWER

Test 34

Group: 2

Verdict: ACCEPTED

Test 35

Group: 2

Verdict: WRONG ANSWER

Test 36

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 3

Verdict: WRONG ANSWER

Test 42

Group: 3

Verdict: WRONG ANSWER

Test 43

Group: 3

Verdict: WRONG ANSWER

Test 44

Group: 3

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: WRONG ANSWER

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: WRONG ANSWER

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: WRONG ANSWER

Test 51

Group: 3

Verdict: WRONG ANSWER

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: WRONG ANSWER

Test 54

Group: 3

Verdict: WRONG ANSWER

Test 55

Group: 3

Verdict: ACCEPTED

Test 56

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 57

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 58

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 59

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 60

Group: 3

Verdict: TIME LIMIT EXCEEDED