QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66038 | #5108. Prehistoric Programs | bili2002# | WA | 5ms | 4220kb | C++17 | 3.9kb | 2022-12-06 00:58:01 | 2022-12-06 00:58:02 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is, pair<T, T2> &p) { is>>p.f>>p.s; return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p) { os<<p.f<<' '<<p.s; return os; }
template<class T> inline istream &operator>>(istream &is, vector<T> &v) { for (auto &id : v) is>>id; return is; }
template<class T> inline ostream &operator<<(ostream &os, const vector<T> &v) { for (auto id : v) os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m) { for (auto id : m) os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um) { for (auto id : um) os<<id<<'\n'; return os; }
template<class T> inline ostream &operator<<(ostream &os, const list<T> &l) { for (auto id : l) os<<id<<' '; return os; }
template<class T> inline ostream &operator<<(ostream &os, const set<T> &s) { for (auto id : s) os<<id<<' '; return os; }
template<class T> inline ostream &operator<<(ostream &os, const unordered_set<T> &us) { for (auto id : us) os<<id<<' '; return os; }
const long long INF = 1e18;
const bool hasTests = 0;
struct par {
int op, cl;
int id;
bool neg;
int highestMin;
bool operator<(const par& oth) {
if (!neg && oth.neg) {
return true;
}
if (neg && !oth.neg) {
return false;
}
if (op - cl > 0 && oth.op - oth.cl <= 0) {
return true;
}
if (op - cl <= 0 && oth.op - oth.cl > 0) {
return false;
}
if (op - cl <= 0) {
return op - cl < oth.op - oth.cl;
} else {
return highestMin > oth.highestMin;
}
}
};
vector<par> p;
bool pos;
vector<int> ans;
int n;
void input() {
cin>>n;
p.resize(n);
string s;
for (int i=0; i<n; i++) {
cin>>s;
p[i].id = i;
p[i].neg = false;
for (auto curr : s) {
if (curr == '(') {
p[i].op++;
} else {
p[i].cl++;
}
if (p[i].op < p[i].cl) {
p[i].neg = true;
}
p[i].highestMin = min(p[i].highestMin, p[i].op - p[i].cl);
}
//cerr<<i<<' '<<p[i].highestMin<<' '<<p[i].neg<<endl;
}
}
void output() {
if (!pos) {
cout<<"impossible"<<endl;
return;
}
cout<<ans<<endl;
}
void solve() {
sort(all(p));
pos = true;
int cntOp = 0, cntCl = 0;
for (auto& curr : p) {
//cout<<curr.id<<' '<<cntOp + curr.highestMin<<' '<<cntCl<<endl;
if (cntOp + curr.highestMin < cntCl) {
pos = false;
break;
}
cntOp += curr.op;
cntCl += curr.cl;
ans.pb(curr.id + 1);
}
if (cntOp != cntCl) {
pos = false;
}
}
void start() {
int t = 1;
if (hasTests) {
cin>>t;
}
for (int i=1; i<=t; i++) {
input();
solve();
//cout<<"Case #"<<i<<": ";
output();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
start();
return 0;
}
/*
7
((((()
()))))
(
)
((
))((
))
3
(((((
)))))((((
))))
2
()
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 4220kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
impossible
result:
wrong answer you didn't find a solution but jury did