QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217794#5108. Prehistoric Programsling__fang_WA 932ms3936kbC++141.6kb2023-10-17 13:17:062023-10-17 13:17:07

Judging History

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

  • [2023-10-17 13:17:07]
  • 评测
  • 测评结果:WA
  • 用时:932ms
  • 内存:3936kb
  • [2023-10-17 13:17:06]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class parenthesis
{
public:
  int left = 0, right = 0;
};

int main()
{
  int n;
  cin >> n;
  vector<parenthesis> p(n);
  vector<int> answer(n);
  int start = -1, end = 0, balance = 0;
  for (int i = 0; i < n; i++)
  {
    string paren;
    cin >> paren;
    for (int j = 0; j < paren.length(); j++)
    {
      if (paren[j] == '(')
      {
        balance++;
        p[i].left++;
      }
      else if (paren[j] == ')' && p[i].left > 0)
      {
        balance--;
        p[i].left--;
      }
      else if (paren[j] == ')' && p[i].left == 0)
      {
        balance--;
        p[i].right++;
      }
    }
    if (p[i].left == 0 && p[i].right != 0)
      end = 1;
    if (p[i].right == 0 && p[i].left != 0 && (start == -1 || p[i].left > p[start].left))
      start = i;
  }
  if (balance != 0 || start == -1 || end == 0)
  {
    balance = 1;
  }
  else
  {
    int quota = p[start].left;
    answer[0] = start;
    p[start].right = -1;
    int next = -1;
    for (int j = 1; j < n; j++)
    {
      for (int i = 0; i < n; i++)
      {
        if (p[i].right <= quota && p[i].right != -1 && (next == -1 || p[i].right < p[next].right))
        {
          next = i;
        }
      }
      if (next == -1)
      {
        balance = 1;
        break;
      }
      quota = quota - p[next].left + p[next].right;
      answer[j] = next;
    }
  }
  if (balance != 0)
  {
    cout << "impossible";
  }
  else
  {
    for (int i = 0; i < n; i++)
      cout << answer[i] + 1 << endl;
  }
}

详细

Test #1:

score: 0
Wrong Answer
time: 932ms
memory: 3936kb

input:

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

output:

41248
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

wrong answer your output is not a permutation of 1...n