QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215235 | #5108. Prehistoric Programs | YYYYYYYY | WA | 6ms | 4428kb | C++14 | 2.3kb | 2023-10-15 07:01:52 | 2023-10-15 07:01:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void processString(int num, vector<array<int, 3>> data);//to store the strings' properties
void selfDefinedSort(vector<array<int, 3>> data);//sort the strings according to self-defined criteria
bool check(int num, vector<array<int, 3>> data);//check if the result is a legal permutation
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int num;
cin >> num;
vector<array<int, 3>> data(num);
processString(num, data);
selfDefinedSort(data);
if(!check(num, data)) cout << "impossible\n";
else {
for(int i = 0; i < num; i++){
cout << data[i][2] << "\n";
}
}
return 0;
}
void processString(int num, vector<array<int, 3>> data){
for(int i = 0; i < num; i++){
string str;
cin >> str;
int mn = 0, total = 0;
for(int j = 0; j < str.length(); j++){
if(str[j] == '(') total++; // (: 1, ): -1
else total--;
mn = min(mn, total);
//minimum is the number of unpaired ')' the string has
}
total -= mn;
//total is the number of unpaired '(' the string has
data[i][0] = total;
data[i][1] = -mn;
data[i][2] = i + 1;
//store the string's index
}
return;
}
void selfDefinedSort(vector<array<int, 3>> data){
//use the built-in sorting for vector and self-define the sorting
sort(data.begin(), data.end(), [&](const array<int, 3> &a, const array<int, 3> &b){
int temp1 = (a[0] == a[1] ? 0 : (a[0] > a[1] ? 1 : -1));
int temp2 = (b[0] == b[1] ? 0 : (b[0] > b[1] ? 1 : -1));
//0 if the string has no unpaired '(', 1 if the string has more '(' than ')', -1 otherwise
if (temp1 != temp2) return temp1 > temp2;
//the larger temporary signal should be placed first
if (temp1 == 1) return a[1] < b[1];
//the string with less unpaired ')' should be placed first
else return a[0] > b[0];
//the string with more unpaired '(' should be placed first
});
return;
}
bool check(int num, vector<array<int, 3>> data){
int mn = 0, total = 0;
for(auto x : data){
mn = min(mn, total - x[1]);
if(mn < 0) return false;
//return false if ')' outnumber '('
total += x[0] - x[1];
}
if(total != 0) return false;
//return false some brackets remain unpaired
return true;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 6ms
memory: 4428kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer wrong output