| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127973 |
2019-07-10T09:42:31 Z |
구재현(#3116) |
JOI15_aaqqz (JOI15_aaqqz) |
C++14 |
|
17 ms |
16888 KB |
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 300005;
int n;
char buf[MAXN];
string s[MAXN];
vector<int> v[MAXN];
string dap;
struct node{
int pos, len;
bool operator<(const node &n)const{
return pi(len, v[len][pos]) < pi(n.len, v[n.len][n.pos]);
}
};
bool Haja(string X){
priority_queue<node> pq;
for(int i=0; i<n; i++) pq.push({i, (int)s[i].size()});
for(int i=X.size()-1; i>=0; i--){
if(X[i] == '1'){
if(pq.empty()) return 1;
auto x = pq.top();
pq.pop();
if(x.len <= i) continue;
if(x.len > i + 1) return 0;
x.len--;
while(x.len > 0 && s[x.pos][x.len - 1] == '0') x.len--;
if(x.len > 0) pq.push(x);
}
}
return pq.empty();
}
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%s", buf);
s[i] = buf;
reverse(s[i].begin(), s[i].end());
}
sort(s, s + n, [&](const string &a, const string &b){
if(a.size() != b.size()) return a.size() < b.size();
for(int i=a.size()-1; i>=0; i--){
if(a[i] != b[i]) return a[i] < b[i];
}
return false;
});
reverse(s, s + n);
v[0].resize(n);
iota(v[0].begin(), v[0].end(), 0);
int p = n;
int B = 0;
for(int i=0; i<n; i++) B = max(B, (int)s[i].size() + i);
for(int i=1; i<=s[0].size(); i++){
while(p > 0 && s[p - 1].size() < i) p--;
vector<int> ze, on;
for(int j=0; j<p; j++){
if(s[j][i - 1] == '0') ze.push_back(j);
else on.push_back(j);
}
sort(ze.begin(), ze.end(), [&](const int &a, const int &b){
return v[i - 1][a] < v[i - 1][b];
});
sort(on.begin(), on.end(), [&](const int &a, const int &b){
return v[i - 1][a] < v[i - 1][b];
});
v[i].resize(p);
for(int j=0; j<ze.size(); j++) v[i][ze[j]] = j;
for(int j=0; j<on.size(); j++) v[i][on[j]] = j + ze.size();
}
string s; s.resize(B + 1);
fill(s.begin(), s.end(), '1');
for(int i=s.size()-1; i>=0; i--){
s[i] = '0';
if(!Haja(s)) s[i] = '1';
}
while(s.back() == '0') s.pop_back();
reverse(s.begin(), s.end());
cout << s << endl;
}
Compilation message
aaqqz.cpp: In function 'int main()':
aaqqz.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<=s[0].size(); i++){
~^~~~~~~~~~~~~
aaqqz.cpp:59:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p > 0 && s[p - 1].size() < i) p--;
~~~~~~~~~~~~~~~~^~~
aaqqz.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<ze.size(); j++) v[i][ze[j]] = j;
~^~~~~~~~~~
aaqqz.cpp:73:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<on.size(); j++) v[i][on[j]] = j + ze.size();
~^~~~~~~~~~
aaqqz.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
aaqqz.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", buf);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
