QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#215570	#5108. Prehistoric Programs	YYYYYYYY	WA	15ms	6292kb	C++14	3.2kb	2023-10-15 11:52:43	2023-10-15 11:52:44

Judging History

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

[2023-10-15 11:52:44]
评测

测评结果：WA
用时：15ms
内存：6292kb

查看

[2023-10-15 11:52:43]
提交

answer

#include <iostream>
#include <cstring>
#include<string> 
#include <vector>

int main() {
    int n = 0;
    std::string parentheses;
    // int in[100000][2]={0};//[),(]
    std::cin >> n;
    int sum = 0;
	std::vector<std::vector<int>> in(n, std::vector<int>(3, 0));

    for (int i = 0; i < n; i++) {
        std::cin >> parentheses;
		int par = 0;
		in[i][2]=i+1;
        while(parentheses[par]!='\0'){
        	if(parentheses[par]=='('){
        		in[i][1] += 1;
			}
			else if(parentheses[par]==')'){
				if(in[i][1]>0){
					in[i][1] -= 1;
				}
				else {
					in[i][0] += 1;
				}
			}
			par++;
		}
		sum += in[i][0]-in[i][1];
		// std::cout<<in[i][0]<<" "<<in[i][1];
    }
    if(sum!=0){
    	std::cout<<"impossible!!"<<sum;
    	return 0;
	}

    std::vector<int> v;
    std::vector<int> value0;
    std::vector<int> value1;
	std::vector<int> right;
	std::vector<int> left;
    int middle = 0;
    int cur[2]={0};
    int flag = 0;
	right.insert(right.begin(),0);
	left.insert(left.begin(),0);
    for(int i = 0; i < n; i++){
        middle = v.size()/2;
		
		if(in[i][1]==0 && in[i][0]!=0){//only)
            // v.push_back(i+1);
            // value0.push_back(in[i][0]);
            // value1.push_back(in[i][1]);
            // flag -= in[i][0];

			right[0] += in[i][0];
			right.push_back(i+1);
         
        }
        else if(in[i][0]==0 && in[i][1]!=0){
        //    v.insert(v.begin(), i+1);
        //    value0.insert(value0.begin(), in[i][0]);
        //    value1.insert(value1.begin(), in[i][1]);
        //    flag += in[i][1];
			left[0] += in[i][1];
			left.push_back(i+1);
          
        }

		else if(v.size()==0){
			// std::cout<<"Y"<<middle;
			v.insert(v.begin()+middle, i+1);
            value0.insert(value0.begin()+middle, in[i][0]);
            value1.insert(value1.begin()+middle, in[i][1]);
		}
        else if(in[i][0]-in[i][1]==0){
            // std::cout<<"-->"<<flag;
            // if(flag >0){
            //     middle++;
            // }
			v.insert(v.begin()+middle, i+1);
            value0.insert(value0.begin()+middle, in[i][0]);
            value1.insert(value1.begin()+middle, in[i][1]);
           
		}
        
    	else if(in[i][0]-in[i][1]>0){//)多，放後
    		 v.push_back(i+1);
            value0.push_back(in[i][0]);
            value1.push_back(in[i][1]);
           
		}
		else if(in[i][0]-in[i][1]<0){
			v.insert(v.begin()+middle, i+1);
            value0.insert(value0.begin()+middle, in[i][0]);
            value1.insert(value1.begin()+middle, in[i][1]);
           
		}
	}

	//v[i] = left+v+right
    sum = left[0];
	// std::cout<<"left"<<left[0]<<"right"<<right[0];
    for(int i = 0; i < v.size(); i++){
        // std::cout<<value0[i]<<"?";
        sum -= value0[i];
        if(sum<0){
            std::cout<<"impossible"; 
    	    return 0;
        }
        sum+=value1[i];
    }
	if(sum-right[0]<0){
		//  std::cout<<"impossible"; 
    	//  return 0;
	}
	for (int i = 1; i < left.size(); i++) {
		std::cout << left[i] << " ";
	}
	for (int i = 0; i < v.size(); i++) {
		std::cout << v[i] << " ";
	}
	for (int i = 1; i < right.size(); i++) {
		std::cout << right[i] << " ";
	}
	
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 15ms

memory: 6292kb

input:

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

output:

1 2 5 7 8 9 10 11 12 14 16 19 23 27 28 30 32 34 35 37 38 42 43 44 54 55 58 59 61 70 72 76 77 79 80 87 91 92 93 94 95 96 97 99 112 116 117 118 120 122 125 126 127 128 130 131 135 136 143 146 147 148 149 150 151 154 161 162 165 166 169 175 176 177 179 181 182 183 184 185 186 187 191 192 193 194 195 19...

result:

ok good plan

Test #2:

score: 0

Accepted

time: 2ms

memory: 3548kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

1 3 10 12 13 14 17 18 20 22 31 33 36 39 54 58 60 62 64 65 66 75 77 80 83 88 89 90 92 97 98 101 104 106 110 122 125 126 127 131 134 135 136 143 147 162 164 166 168 171 177 178 179 181 182 188 189 190 198 206 208 209 212 213 214 215 216 217 223 228 229 239 242 243 245 247 252 253 257 258 265 267 268 2...

result:

ok good plan

Test #3:

score: 0

Accepted

time: 0ms

memory: 3424kb

input:

2
()
()

output:

2 1

result:

ok good plan

Test #4:

score: 0

Accepted

time: 1ms

memory: 3484kb

input:

2
((
))

output:

1 2

result:

ok good plan

Test #5:

score: 0

Accepted

time: 0ms

memory: 3464kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0

Accepted

time: 0ms

memory: 3408kb

input:

3
()
(
)

output:

2 1 3

result:

ok good plan

Test #7:

score: 0

Accepted

time: 0ms

memory: 3412kb

input:

3
)(
(
)

output:

2 1 3

result:

ok good plan

Test #8:

score: 0

Accepted

time: 0ms

memory: 3424kb

input:

5
))(
(()
)(
(
)

output:

2 4 3 1 5

result:

ok good plan

Test #9:

score: 0

Accepted

time: 0ms

memory: 3400kb

input:

3
((
))())
(

output:

1 3 2

result:

ok good plan

Test #10:

score: -100

Wrong Answer

time: 0ms

memory: 3496kb

input:

6
)
()
()()()
((
)
)

output:

impossible!!1

result:

wrong answer wrong plan (expected impossible)