QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215235#5108. Prehistoric ProgramsYYYYYYYYWA 6ms4428kbC++142.3kb2023-10-15 07:01:522023-10-15 07:01:53

Judging History

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

  • [2023-10-15 07:01:53]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:4428kb
  • [2023-10-15 07:01:52]
  • 提交

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;
}

詳細信息

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