| Task: | Key cutting |
| Sender: | ä |
| Submission time: | 2024-11-16 14:40:01 +0200 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | WRONG ANSWER |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | WRONG ANSWER | 0.00 s | details |
| #3 | ACCEPTED | 0.00 s | details |
| #4 | WRONG ANSWER | 0.00 s | details |
| #5 | WRONG ANSWER | 0.00 s | details |
| #6 | WRONG ANSWER | 0.00 s | details |
| #7 | WRONG ANSWER | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | WRONG ANSWER | 0.03 s | details |
| #10 | WRONG ANSWER | 0.03 s | details |
| #11 | WRONG ANSWER | 0.03 s | details |
| #12 | WRONG ANSWER | 0.03 s | details |
| #13 | WRONG ANSWER | 0.04 s | details |
| #14 | WRONG ANSWER | 0.04 s | details |
Compiler report
input/code.cpp: In function 'int main()':
input/code.cpp:45:18: warning: unused variable 'ok' [-Wunused-variable]
45 | bool ok = true;
| ^~
input/code.cpp:47:17: warning: unused variable 'mi2' [-Wunused-variable]
47 | int mi2 = 1000000001;
| ^~~Code
#include <bits/stdc++.h>
// g++ -std=c++17 k.cpp -o k
using namespace std;
int s[10101010];
int n;
unordered_map<int, int> lahin;
int hae(int a, int b){
a +=n; b+=n;
int mi = 1000000001;
while(a<=b){
if(a%2==1) mi = min(mi, s[a++]);
if(a%2==0) mi = min(mi, s[b--]);
a/=2; b/=2;
}
return mi;
}
void add(int k, int x){
k+=n;
s[k]=x;
for (k /=2; k>=1; k/=2){
s[k] = min(s[k*2], s[k*2+1]);
}
}
int main() {
cin >> n;
for (int i = 0; i < n;++i){
int oof;
cin >> oof;
add(i, oof);
}
unordered_set<int> f;
int cuts = 0;
for (int i = 0; i < n; ++i){
auto coun = lahin.count(s[i+n]);
//cout << "etsitaaan " << s[i+n] << " " << coun << endl;
if (coun==0){
//cout << "ei loyd " << i << " " << s[i+n] << endl;
cuts += 1;
lahin[s[i+n]] = i;
} else {
auto lah = lahin[s[i+n]];
bool ok = true;
int mi = hae(lah+1, i);
int mi2 = 1000000001;
//for (int j = i-1; j > lah; --j){
// mi2 = min(mi2, s[j+n]);
//}
///cout << "loyd " << mi << " " << s[i+n] << endl;
if (mi < s[i+n]){
//cout << "lis 1" << endl;
cuts += 1;
}
lahin[s[i+n]] = i;
}
}
cout << cuts << endl;
return 0;
}Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| 3 1 2 1 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 2
Verdict: WRONG ANSWER
| input |
|---|
| 1 0 |
| correct output |
|---|
| 0 |
| user output |
|---|
| 1 |
Test 3
Verdict: ACCEPTED
| input |
|---|
| 1 9 |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 4
Verdict: WRONG ANSWER
| input |
|---|
| 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
| correct output |
|---|
| 0 |
| user output |
|---|
| 1 |
Test 5
Verdict: WRONG ANSWER
| input |
|---|
| 100 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ... |
| correct output |
|---|
| 25 |
| user output |
|---|
| 26 |
Test 6
Verdict: WRONG ANSWER
| input |
|---|
| 100 2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ... |
| correct output |
|---|
| 41 |
| user output |
|---|
| 42 |
Test 7
Verdict: WRONG ANSWER
| input |
|---|
| 100 36 5 10 37 94 59 20 31 64 2 58... |
| correct output |
|---|
| 99 |
| user output |
|---|
| 100 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| 100 228768416 32415139 952687252 6... |
| correct output |
|---|
| 100 |
| user output |
|---|
| 100 |
Test 9
Verdict: WRONG ANSWER
| input |
|---|
| 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
| correct output |
|---|
| 0 |
| user output |
|---|
| 1 |
Test 10
Verdict: WRONG ANSWER
| input |
|---|
| 100000 1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ... |
| correct output |
|---|
| 24965 |
| user output |
|---|
| 24966 |
Test 11
Verdict: WRONG ANSWER
| input |
|---|
| 100000 2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ... |
| correct output |
|---|
| 38968 |
| user output |
|---|
| 38969 |
Test 12
Verdict: WRONG ANSWER
| input |
|---|
| 100000 4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ... |
| correct output |
|---|
| 59156 |
| user output |
|---|
| 59157 |
Test 13
Verdict: WRONG ANSWER
| input |
|---|
| 100000 18 5 6 16 8 10 1 7 4 15 5 9 19... |
| correct output |
|---|
| 82598 |
| user output |
|---|
| 82599 |
Test 14
Verdict: WRONG ANSWER
| input |
|---|
| 100000 33 37 37 86 42 38 18 10 77 57 ... |
| correct output |
|---|
| 94897 |
| user output |
|---|
| 94898 |
