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;

	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