Submission #127973

# Submission time Handle Problem Language Result Execution time Memory
127973 2019-07-10T09:42:31 Z 구재현(#3116) JOI15_aaqqz (JOI15_aaqqz) C++14
0 / 100
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 -