QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#214645	#5108. Prehistoric Programs	YYYYYYYY	WA	21ms	5016kb	C++14	2.9kb	2023-10-14 22:31:05	2023-10-14 22:31:05

Judging History

你现在查看的是最新测评结果

[2023-10-14 22:31:05]
评测

测评结果：WA
用时：21ms
内存：5016kb

查看

[2023-10-14 22:31:05]
提交

answer

#include <iostream>
#include <string>

void processString(int info[4], int num){
    int left = 0, right = 0;
    std::string str;
    std::cin >> str;
    for(int i = 0; i < str.length(); i++){
        if(str[i] == '(') {
            right++;
        } else if(str[i] == ')'){
            if(right == 0) left++;
            else right--;
        }
    } 
    info[0] = num + 1;
    info[1] = left; //need how many parenthesis on its left
    info[2] = right; //need how many parenthesis on its right
    info[3] = right - left; //the total sum of the string
    return;
}

void swap(int arr1[4], int arr2[4]){
    int temp0 = arr1[0], temp1 = arr1[1], temp2 = arr1[2], temp3 = arr1[3];
    arr1[0] = arr2[0];
    arr1[1] = arr2[1];
    arr1[2] = arr2[2];
    arr1[3] = arr2[3];
    arr2[0] = temp0;
    arr2[1] = temp1;
    arr2[2] = temp2;
    arr2[3] = temp3;
    return;
}

int selfDefinedCompare(int arr1[4], int arr2[4]){
    if(arr1[3] >= 0 && arr2[3] < 0) return 3;
    if(arr1[3] <= 0 && arr2[3] > 0) return 1;
    if(arr1[3] < 0){
        if(arr1[2] > arr2[2]) return 3;
        if(arr1[2] < arr2[2]) return 1;
        if(arr1[0] > arr2[0]) return 1;
        if(arr1[0] < arr2[0]) return 3;
    }
    if(arr1[3] > 0){
        if(arr1[1] > arr2[1]) return 1;
        if(arr1[1] < arr2[1]) return 3;
        if(arr1[0] > arr2[0]) return 1;
        if(arr1[0] < arr2[0]) return 3;
    }
    if(arr1[0] > arr2[0]) return 1;
    if(arr1[0] < arr2[0]) return 3;
}

 
int partition(int info[][4], int start, int end){
    int* pivot = info[start];
    int count = 0;
    for (int i = start + 1; i <= end; i++) {
        if (selfDefinedCompare(info[i], pivot) > 1)
            count++;
    }
    int pivotIndex = start + count;
    swap(info[pivotIndex], info[start]);
    int i = start, j = end;
    while (i < pivotIndex && j > pivotIndex){
        while (selfDefinedCompare(info[i], pivot) == 3){
            i++;
        }
        while (selfDefinedCompare(info[j], pivot) == 1){
            j--;
        }
        if (i < pivotIndex && j > pivotIndex){
            swap(info[i++], info[j--]);
        }
    }
    return pivotIndex;
}
 
void quickSort(int info[][4], int start, int end){
    if (start >= end)
        return;
    int p = partition(info, start, end);
    quickSort(info, start, p - 1);
    quickSort(info, p + 1, end);
}

bool check(int num, int info[][4]){
    int temp = 0;
    for(int i = 0; i < num; i++){
        temp -= info[i][1];
        if(temp < 0) return false;
        temp += info[i][2];
    }
    return temp == 0;
}

int main() {
    int num, info[100000][4];
    std::cin >> num;
    for(int i = 0; i < num; i++) processString(info[i], i);
    quickSort(info, 0, num - 1);
    if(check(num, info)){
        for(int i = 0; i < num; i++){
            std::cout << info[i][0] << "\n";
        }
    } else{
        std::cout << "impossible";
    }
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 0

Wrong Answer

time: 21ms

memory: 5016kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

impossible

result:

wrong answer you didn't find a solution but jury did