Submission #554721

#	Time	Username	Problem	Language	Result	Execution time	Memory
554721		Arvin	Super Dango Maker (JOI22_dango3)	C++17	7 / 100	787 ms	95060 KiB

dango3

#include "dango3.h"
#include <bits/stdc++.h>

using namespace std;

//namespace {
//	int variable_example = 1;
//}  // namespace

map<vector<int>, int> mp;

void Solve(int n, int m) {
	int len = n*m;
	
	vector<int> v;
	for(int x=0;x<len;x++){
		v.push_back(x+1);
	}
	
	auto ask = [&](vector<int> &v) -> int {
		if(mp.count(v)) return mp[v];
		return mp[v] = Query(v);
	};
	
	vector<int> comp[n];
	vector<int> w = v;
	vector<int> ans;
	int pos = 0;
	while(pos < w.size() && ans.size()+1 < n){
		int bound = 0;
		int left = pos, right = w.size()-1;
		while(left <= right){
			int mid = (left+right) >> 1;
			
			vector<int> z = ans;
			for(int x=mid;x<w.size();x++){
				z.push_back(w[x]);
			}
			
			if(ask(z) > 0){
				bound = mid;
				left = mid+1;
			} else {
				right = mid-1;
			}
		}
		
		ans.push_back(w[bound]);
		pos = bound+1;
	}
	ans.push_back(w.back());
	
	v.clear();
	pos = 0;
	for(int x=0;x<w.size();x++){
		while(pos < ans.size() && ans[pos] < w[x]){
			pos++;
		}
		if(pos < ans.size() && ans[pos] == w[x]) continue;
		
		v.push_back(w[x]);
	}
	
	int c[len];
	fill(c, c+len, -1);
	
	for(int x=0;x<ans.size();x++){
		c[ans[x]-1] = x;
	}
	
	for(int x=0;x<ans.size();x++){
		for(int y=0;y<v.size();y+=n){
			queue<pair<int, int>> q;
			q.push({y, min(y+n, (int) v.size())-1});
			
			while(!q.empty()){
				pair<int, int> p = q.front();
				q.pop();
				
				if(p.first > p.second) continue;
//				
//				cout << ans[x] << " " << p.first << " " << p.second << "\n";
//				
				vector<int> w;
				for(int z=0;z<ans.size();z++){
					if(z == x) continue;
					w.push_back(ans[z]);
				}
				for(int z=p.first;z<=p.second;z++){
					if(c[v[z]-1] == -1) w.push_back(v[z]);
				}
				
				if(ask(w) > 0){
					if(p.first == p.second){
						c[v[p.first]-1] = c[ans[x]-1];	
						continue;
					}
					
					q.push({p.first, (p.first+p.second)/2});
					q.push({(p.first+p.second)/2 + 1, p.second});
				}
			}
		}
	}
	
	Answer(ans);
	for(int x=0;x<v.size();x++){
		comp[c[v[x]-1]].push_back(v[x]);
	}
	
	for(int x=0;x<m-1;x++){
		vector<int> w;
		for(int y=0;y<n;y++){
			w.push_back(comp[y][x]);
		}
		
		Answer(w);
	}
}

Compilation message (stderr)

dango3.cpp: In function 'void Solve(int, int)':
dango3.cpp:29:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  while(pos < w.size() && ans.size()+1 < n){
      |        ~~~~^~~~~~~~~~
dango3.cpp:29:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  while(pos < w.size() && ans.size()+1 < n){
      |                          ~~~~~~~~~~~~~^~~
dango3.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int x=mid;x<w.size();x++){
      |                  ~^~~~~~~~~
dango3.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int x=0;x<w.size();x++){
      |              ~^~~~~~~~~
dango3.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while(pos < ans.size() && ans[pos] < w[x]){
      |         ~~~~^~~~~~~~~~~~
dango3.cpp:59:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(pos < ans.size() && ans[pos] == w[x]) continue;
      |      ~~~~^~~~~~~~~~~~
dango3.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int x=0;x<ans.size();x++){
      |              ~^~~~~~~~~~~
dango3.cpp:71:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int x=0;x<ans.size();x++){
      |              ~^~~~~~~~~~~
dango3.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int y=0;y<v.size();y+=n){
      |               ~^~~~~~~~~
dango3.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int z=0;z<ans.size();z++){
      |                 ~^~~~~~~~~~~
dango3.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 78