QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215570#5108. Prehistoric ProgramsYYYYYYYYWA 15ms6292kbC++143.2kb2023-10-15 11:52:432023-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;
}

Details

Tip: Click on the bar to expand more detailed information

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)