QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #362924 | #3506. Team Contest | eric | 0 | 1ms | 7792kb | C++14 | 6.8kb | 2024-03-23 17:36:35 | 2024-03-23 17:36:36 |
answer
#include <bits/stdc++.h>
using namespace std;
#define N 150007
typedef struct {
int a;
int b;
int c;
} member_score_t;
typedef struct {
int id;
int score;
} score_id_t;
member_score_t score_db[N];
bool valid_node[N] = {0};
score_id_t A_score[N];
score_id_t B_score[N];
score_id_t C_score[N];
bool cmp (const score_id_t & x, const score_id_t & y)
{
if (x.score > y.score)
return true;
if (x.id < y.id)
return true;
return false;
}
static void print_db (int n)
{
printf(" A B C\n");
for (int i = 0; i < n; i++) {
printf("(%4d,%4d,%4d) %4d(%4d) %4d(%4d) %4d(%4d)\n",
score_db[i].a, score_db[i].b, score_db[i].c,
A_score[i].score, A_score[i].id,
B_score[i].score, B_score[i].id,
C_score[i].score, C_score[i].id);
}
}
int main ()
{
int n;
cin >> n;
for(int x = 0; x < n; x++) {
cin >> score_db[x].a >> score_db[x].b >> score_db[x].c;
A_score[x].id = B_score[x].id = C_score[x].id = x;
A_score[x].score = score_db[x].a;
B_score[x].score = score_db[x].b;
C_score[x].score = score_db[x].c;
valid_node[x] = true;
}
sort(A_score, A_score+n, cmp);
sort(B_score, B_score+n, cmp);
sort(C_score, C_score+n, cmp);
// print_db(n);
// Main loop looking for the best option
int i = 0, j = 0, k = 0;
while (i < n && j < n && k < n) {
if (A_score[i].id == B_score[j].id && B_score[j].id == C_score[k].id) {
//printf("A == B == C \n");
valid_node[A_score[i].id] = false;
i++;
j++;
k++;
}
else if (A_score[i].id == B_score[j].id) {
//printf("A == B \n");
valid_node[A_score[i].id] = false;
do { i++; } while(i < n && valid_node[A_score[i].id] == false);
do { j++; } while(j < n && valid_node[B_score[j].id] == false);
}
else if (B_score[j].id == C_score[k].id) {
//printf("B == C \n");
valid_node[B_score[j].id] = false;
do { j++; } while(j < n && valid_node[B_score[j].id] == false);
do { k++; } while(k < n && valid_node[C_score[k].id] == false);
}
else if (C_score[k].id == A_score[i].id) {
//printf("C == A \n");
valid_node[C_score[k].id] = false;
do { k++; } while(k < n && valid_node[C_score[k].id] == false);
do { i++; } while(i < n && valid_node[A_score[i].id] == false);
}
else {
// In this case, A/B/C are from different id
// However, there could still be same value risk;
int A, B, C;
bool error = false;
A = A_score[i].id;
B = B_score[j].id;
C = C_score[k].id;
#if 0
if (A > B) {
if (B > C) {
// A > B > C
}
else if (C > A) {
// C > A > B
}
else {
// A > C > B
}
}
else {
if (A > C) {
// B > A > C
}
else if (B > C) {
// B > C > A
}
else {
// C > B > A
}
}
#else
//printf("A is %d, B is %d, C is %d \n", A, B, C);
for (int ii = i; ii < n && A_score[ii].score == A_score[i].score; ii++) {
if (A_score[ii].id > B && A_score[ii].id > C) {
break;
}
if (valid_node[A_score[ii].id] == false) {
continue;
}
if (A_score[ii].id == B) {
error = true;
valid_node[B] = false;
do { j++; } while(j < n && valid_node[B_score[j].id] == false);
break;
}
if (A_score[ii].id == C) {
error = true;
valid_node[C] = false;
do { k++; } while(k < n && valid_node[C_score[k].id] == false);
break;
}
}
if (error) continue;
for (int jj = j; jj < n && B_score[jj].score == B_score[j].score; jj++) {
if (B_score[jj].id > C && B_score[jj].id > A) {
break;
}
if (valid_node[B_score[jj].id] == false) {
continue;
}
if (B_score[jj].id == C) {
error = true;
valid_node[C] = false;
do { k++; } while(k < n && valid_node[C_score[k].id] == false);
break;
}
if (B_score[jj].id == A) {
error = true;
valid_node[A] = false;
do { i++; } while(i < n && valid_node[A_score[i].id] == false);
break;
}
}
if (error) continue;
for (int kk = k; kk < n && C_score[kk].score == C_score[k].score; kk++) {
if (C_score[kk].id > B && C_score[kk].id > A) {
break;
}
if (valid_node[C_score[kk].id] == false) {
continue;
}
if (C_score[kk].id == B) {
error = true;
valid_node[B] = false;
do { j++; } while(j < n && valid_node[B_score[j].id] == false);
break;
}
if (C_score[kk].id == A) {
error = true;
valid_node[A] = false;
do { i++; } while(i < n && valid_node[A_score[i].id] == false);
break;
}
}
if (error) continue;
#endif
//printf("Node %d, %d, %d are selected\n", A_score[i].id, B_score[j].id, C_score[k].id);
int idx;
idx = A_score[i].id;
A = score_db[idx].a;
//printf("(%d,%d,%d)\n", score_db[idx].a, score_db[idx].b, score_db[idx].c);
idx = B_score[j].id;
B = score_db[idx].b;
//printf("(%d,%d,%d)\n", score_db[idx].a, score_db[idx].b, score_db[idx].c);
idx = C_score[k].id;
C = score_db[idx].c;
//printf("(%d,%d,%d)\n", score_db[idx].a, score_db[idx].b, score_db[idx].c);
cout << A+B+C << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 8
Accepted
time: 1ms
memory: 5712kb
input:
3 1 1 2 1 2 1 2 1 1
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
3 1 2 2 2 1 2 2 2 1
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7788kb
input:
3 3 3 3 2 2 2 1 1 1
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
4 3 1 1 2 2 2 1 1 3 1 2 1
output:
8
result:
ok single line: '8'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
3 1 2 3 1 3 4 1 4 2
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 7752kb
input:
3 4 1 3 3 1 2 2 1 4
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
3 2 4 1 4 3 1 3 2 1
output:
-1
result:
ok single line: '-1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
3 9 9 1 9 9 2 9 9 3
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 7792kb
input:
3 9 2 9 9 3 9 9 1 9
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
3 3 9 9 1 9 9 2 9 9
output:
-1
result:
ok single line: '-1'
Test #11:
score: -8
Runtime Error
input:
300 57761889 84542255 27050597 34660889 31001456 73541706 28145521 16239284 59747407 28301910 73147643 52729219 76934759 81682223 25122810 79313872 51831684 8459494 79291107 42746492 28469171 178085 36381730 88571483 88031596 68636497 47738858 78328954 72492907 81005026 20116327 27194915 29047676 15...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #36:
score: 0
Time Limit Exceeded
input:
150000 3 3 1 2 5 5 1 3 5 4 3 5 3 4 4 4 4 2 4 3 5 5 1 2 5 4 1 2 3 3 4 4 5 3 3 5 2 4 3 1 3 2 5 2 4 4 5 3 2 5 1 5 4 3 3 2 5 1 1 4 3 2 5 2 3 5 3 3 4 1 3 4 2 4 3 1 5 4 2 1 4 1 4 4 5 4 3 4 5 3 2 1 2 5 4 5 4 5 4 5 1 2 1 4 1 3 1 4 2 5 2 3 5 3 3 4 2 5 1 4 5 2 1 1 2 2 1 3 2 5 4 3 5 4 5 3 2 4 5 5 2 5 3 3 3 4 4...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%