— Dark mode

Datatähti 2025 alku

Kortit I

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
CSES - Datatähti 2025 alku - Results
Submission details
Task:Kortit I
Sender:TNT
Submission time:2024-11-06 18:00:25 +0200
Language:C++ (C++17)
Status:READY
Result:12
Feedback
groupverdictscore
#1ACCEPTED12
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3details
#2--2, 3details
#3--3details
#4--3details
#5--3details
#6--3details
#7--3details
#8--3details
#9--3details
#10--3details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details
#16--3details
#17--3details
#18--3details
#19--3details
#20--3details

Compiler report

input/code.cpp: In function 'Output PlayGame(std::vector<int>)':
input/code.cpp:120:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                 for (int i = 0; i < Permutations.size()-1; i++) {
      |                                 ~~^~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:136:38: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  136 |                                 auto t2 = std::chrono::high_resolution_clock::now();
      |                                      ^~
input/code.cpp:116:14: warning: variable 't1' set but not used [-Wunused-but-set-variable]
  116 |         auto t1 = std::chrono::high_resolution_clock::now();
      |              ^~
input/code.cpp:143:14: warning: variable 't2' set but not used [-Wunused-but-set-variable]
  143 |         auto t2 = std::chrono::high_resolution_clock::now();
      |              ^~

Code

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <chrono>

struct Output {
	std::string Possible = "NO";
	bool True = false;
	std::vector<int> GamePlayerA;
	std::vector<int> GamePlayerB;
};

/*unsigned long factorial(const int n)
{
    unsigned long f = 1;
    for (unsigned long i=1; i<=(unsigned long)n; i++)
      f = static_cast<unsigned long>(f*i);
			std::cout << f << "\n";
    return f;
}*/

Output PlayGame(std::vector<int> inputs) {
	const int n = inputs[0];
	const int PointsA = inputs[1];
	const int PointsB = inputs[2];
	Output Result;
	if (PointsA+PointsB > n) {
		return Result;
	}

	std::vector<std::vector<int>> Permutations;
	//std::cout << "start\n";
	/*unsigned long TotalPermCount = factorial(n);
	throw;
	std::cout << TotalPermCount << "\n";
	Permutations.reserve(TotalPermCount);
	Permutations.resize(TotalPermCount);*/

	Permutations.push_back({});
	for (int i = 0; i<n; i++) {
		Permutations[0].push_back(i+1);
	}
	//std::cout << "Perm "<< Permutations[0].size() << "\n\n";

	// If no points
	if ((PointsA==0) && (PointsB == 0)) {
		Result.Possible = "YES";
		Result.True = true;
		Result.GamePlayerA = Permutations[0];
		Result.GamePlayerB = Permutations[0];
		return Result;
	}

	/*auto t1 = std::chrono::high_resolution_clock::now();
	while (std::next_permutation(Permutations[0].begin(), Permutations[0].end())) {
		Permutations.push_back(Permutations[0]);
	};
	int P = 0;
	do {
		Permutations[P] = Permutations[0];
		P++;
	} while (std::next_permutation(Permutations[0].begin(), Permutations[0].end()));
	auto t2 = std::chrono::high_resolution_clock::now();
	std::cout << "permutations took: " << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count() << "\n";
	*/
	//auto t1 = std::chrono::high_resolution_clock::now();
	/*for (int i = 0; i < Permutations.size(); i++) {
		std::cout << "Permutation: " << i << "\n";
		for (int j = i; j >= 0; j--) {
			std::cout << "Inner Permutation: " << j << "\n";
			int PointA = 0;
			int PointB = 0;
			for (int k = 0; k<n; k++) {
				if (Permutations[i][k] > Permutations[j][k]) {
					PointA++;
				} else if (Permutations[i][k] < Permutations[j][k]) {
					PointB++;
				};
			}
			if (PointA==PointsA && PointB == PointsB) {
				Result.Possible = "YES";
				Result.True = true;
				Result.GamePlayerA = Permutations[i];
				Result.GamePlayerB = Permutations[j];
				auto t2 = std::chrono::high_resolution_clock::now();
				std::cout << "Loops took: " << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count() << "\n";
				return Result;
			}
		}
	}*/

	auto Og = Permutations[0];
	// If points = max points
	if (PointsA+PointsB==n) {
		if ((PointsA == n || PointsB == n)) return Result;
		Result.Possible = "YES";
		Result.True = true;

		if (PointsA >= PointsB) {
			std::rotate(Permutations[0].begin(), Permutations[0].begin() +PointsB, Permutations[0].end());
			Result.GamePlayerA = Permutations[0];
			Result.GamePlayerB = Og;
		} else if (PointsA < PointsB) {
			std::rotate(Permutations[0].begin(), Permutations[0].begin() +PointsA, Permutations[0].end());
			Result.GamePlayerA = Og;
			Result.GamePlayerB = Permutations[0];
		}

		return Result;
	}
	if (PointsA>(n/2) && PointsB>(n/2)) {
		return Result;
	}

	auto t1 = std::chrono::high_resolution_clock::now();
	while (std::next_permutation(Og.begin(), Og.end())) {
		Permutations.push_back(Og);
		auto cur = Permutations.back();
		for (int i = 0; i < Permutations.size()-1; i++) {
			int PointA = 0;
			int PointB = 0;
			for (int k = 0; k<n; k++) {
				if (Permutations[i][k] > cur[k]) {
					PointA++;
				} else if (Permutations[i][k] < cur[k]) {
					PointB++;
				};
			}
			//std::cout << PointA << " " << PointB << "\n";
			if (PointA==PointsA && PointB == PointsB) {
				Result.Possible = "YES";
				Result.True = true;
				Result.GamePlayerA = Permutations[i];
				Result.GamePlayerB = cur;
				auto t2 = std::chrono::high_resolution_clock::now();
				//std::cout << "Loops took: " << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count() << "\n";
				return Result;
			}
		}
	}

	auto t2 = std::chrono::high_resolution_clock::now();
	//std::cout << "Loops took: " << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count() << "\n";
	return Result;
}

int main () {
	// Input
	// t = number of games
	// n = number of cards from 1 to n
	// a = points of a
	// b = points of b
	int t, n, a, b;
	std::cin >> t;
	std::vector<std::vector<int>> inputs;
	inputs.reserve(t);
	inputs.resize(t);
	for (int i=0; i<t; i++) {
		std::cin >> n >> a >> b;
		inputs[i] = {n,a,b};
	};

		//Goal: find if a game is possible and if true, find a possible game.
		//Player with the higher card gets 1 point
		//If cards are the same, 0 points
		for (const std::vector<int> &input : inputs) {
			Output Output = PlayGame(input);
			//std::cout << "out" << "\n\n";

			std::cout << Output.Possible << "\n";
			if (Output.True) {
				for (const int i : Output.GamePlayerA) {
					std::cout << i << " ";
				}
				std::cout << "\n";
				for (const int i : Output.GamePlayerB) {
					std::cout << i << " ";
				}
				std::cout << "\n";
			}
		}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
54
4 4 0
3 1 3
3 2 2
4 0 4
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
NO
NO
NO
NO
NO
...
view save

Test 2

Group: 2, 3

Verdict:

input
284
6 1 0
5 0 2
7 1 5
7 7 5
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 
2 3 4 5 6 1 7 
...
view save

user output
(empty)

Test 3

Group: 3

Verdict:

input
955
14 2 10
12 2 5
10 4 9
14 1 13
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 4

Group: 3

Verdict:

input
869
17 12 9
16 8 4
15 9 9
17 11 15
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 5

Group: 3

Verdict:

input
761
18 3 15
19 1 15
18 8 1
19 19 17
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 6

Group: 3

Verdict:

input
925
21 14 21
20 18 18
20 7 6
21 14 9
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 7

Group: 3

Verdict:

input
529
22 3 3
22 17 5
22 6 15
22 22 20
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 8

Group: 3

Verdict:

input
576
23 18 9
23 16 8
23 16 13
23 16 22
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Test 9

Group: 3

Verdict:

input
625
24 2 22
24 15 21
24 6 3
24 21 1
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 10

Group: 3

Verdict:

input
676
25 16 25
25 15 2
25 15 7
25 15 16
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 11

Group: 3

Verdict:

input
729
26 2 18
26 14 18
26 5 18
26 19 13
...
view save

correct output
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 12

Group: 3

Verdict:

input
784
27 26 7
27 14 0
27 14 5
27 14 14
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 13

Group: 3

Verdict:

input
841
28 26 16
28 13 19
28 5 8
28 26 4
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 14

Group: 3

Verdict:

input
900
29 24 15
29 13 2
29 13 7
29 13 16
...
view save

correct output
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 15

Group: 3

Verdict:

input
961
30 24 26
30 12 24
30 4 29
30 24 14
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
(empty)

Test 16

Group: 3

Verdict:

input
1000
15 12 6
33 18 30
44 4 26
6 6 5
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 17

Group: 3

Verdict:

input
1000
45 32 30
4 0 3
46 23 10
71 19 46
...
view save

correct output
NO
NO
YES
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Test 18

Group: 3

Verdict:

input
1000
51 29 37
75 11 72
5 2 4
31 8 26
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
(empty)

Test 19

Group: 3

Verdict:

input
1000
50 20 37
99 45 58
86 79 73
85 70 54
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Test 20

Group: 3

Verdict:

input
1000
26 23 5
73 53 59
64 47 41
80 75 55
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (TNT)

2024-11-06 18:32:58 272024-11-06 18:30:45 272024-11-06 18:00:25 122024-11-06 17:57:52 02024-11-03 17:06:01 122024-11-03 16:13:55 02024-11-03 16:06:25 02024-11-03 16:05:56 02024-11-03 15:37:18 122024-11-03 15:34:36 02024-11-03 13:59:39 02024-11-03 12:42:05 12