CSES - Datatähti 2021 loppu - Results
Submission details
Task:Järjestäminen
Sender:lady-stardust
Submission time:2021-01-23 19:52:09 +0200
Language:C++ (C++17)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.07 s1, 2details
#20.07 s2details
#30.07 s1, 2details
#40.07 s1, 2details

Compiler report

input/code.cpp: In function 'bool explore()':
input/code.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < current.size() - 3; i++) {
                  ~~^~~~~~~~~~~~~~~~~~~~
input/code.cpp:31:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i + 2; j < current.size() - 1; j++) {
                       ~~^~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define ull unsigned long long
using namespace std;
unordered_map<string, bool> m0;
unordered_map<string, bool> m;
unordered_map<string, bool> m2;
string current = "";
string target = "";
void reset() {
// memset(arr, 0, sizeof(arr));
m = {};
m2 = {};
current = "";
target = "";
}
bool explore() {
if (current == target) return true;
if (m2[current]) return true;
if (m[current]) return false;
m[current] = true;
for (int i = 0; i < current.size() - 3; i++) {
for (int j = i + 2; j < current.size() - 1; j++) {
swap(current[i], current[j]);
swap(current[i+1], current[j+1]);
if (explore()) return true;
swap(current[i], current[j]);
swap(current[i + 1], current[j + 1]);
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
istringstream cin(R"(3
2
1 2
5
2 3 5 1 4
7
5 3 4 2 1 6 7)");
ll t; cin >> t;
///
current = "12345678";
target = "";
explore();
for (auto x : m) m2[x.first] = true;
reset();
///
current = "1234567";
target = "";
explore();
for (auto x : m) m2[x.first] = true;
reset();
///
current = "123456";
target = "";
explore();
for (auto x : m) m2[x.first] = true;
reset();
///
current = "12345";
target = "";
explore();
for (auto x : m) m2[x.first] = true;
reset();
///
current = "1234";
target = "";
explore();
for (auto x : m) m2[x.first] = true;
reset();
for (int i = 0; i < t; i++) {
char n; cin >> n;
reset();
for (int j = '1'; j <= n; j++) {
char x; cin >> x;
current += x;
target += j;
}
if (explore()) {
cout << "YES" << "\n";
//for (auto x : m) {
//m2[x.first] = true;
//}
} else {
cout << "NO" << "\n";
}
}
//cout << x;
}

Test details

Test 1

Group: 1, 2

Verdict:

input
153
1
1
2
1 2
...

correct output
YES
YES
NO
NO
NO
...

user output
YES
YES
NO

Test 2

Group: 2

Verdict:

input
1000
59
35 29 32 50 11 15 9 21 19 45 2...

correct output
YES
NO
YES
NO
YES
...

user output
YES
YES
NO

Test 3

Group: 1, 2

Verdict:

input
720
6
1 6 4 5 2 3
6
6 3 2 1 5 4
...

correct output
YES
NO
NO
NO
YES
...

user output
YES
YES
NO

Test 4

Group: 1, 2

Verdict:

input
1000
8
7 4 2 8 6 3 5 1
8
3 8 2 7 5 4 6 1
...

correct output
NO
NO
YES
NO
YES
...

user output
YES
YES
NO