oj.uz

Submission #555814

# Submission time Handle Problem Language Result Execution time Memory
555814 2022-05-01T15:29:12 Z Arvin Super Dango Maker (JOI22_dango3) C++17
22 / 100
 4307 ms 1048576 KB 
#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;
	
	auto ask = [&](vector<int> &v) -> int {
		if(mp.count(v)) return mp[v];
		return mp[v] = Query(v);
	};
	
	vector<int> comp[m+1];
	int idx = 0;
	
	comp[idx].push_back(1);
	for(int x=2;x<=len;x++){
		int pos = idx+1;
		int left = 0, right = idx;
		while(left <= right){
			int mid = (left+right) >> 1;
			
			bool exist[len+1];
			fill(exist, exist+len+1, true);
			
			exist[x] = false;
			for(int y=0;y<=mid;y++){
				for(auto idx : comp[y]){
					exist[idx] = false;
				}
			}
			
			vector<int> w;
			for(int y=1;y<=len;y++){
				if(exist[y]) w.push_back(y);
			}
			
//			cout << x << " " << idx << " -> " << " " << mid << " " << ask(w) << "\n";
			if(ask(w) == m-(mid+1)){
				pos = mid;
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		
//		cout << x << " = " << pos << "\n";
		comp[pos].push_back(x);
		idx = max(idx, pos);
	}
	
	for(int x=0;x<m;x++){
		vector<int> w;
		for(int y=0;y<n;y++){
			w.push_back(comp[x][y]);
		}
		
		Answer(w);
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7580 KB Output is correct
2 Correct 39 ms 7224 KB Output is correct
3 Correct 54 ms 10676 KB Output is correct
4 Correct 51 ms 10672 KB Output is correct
5 Correct 28 ms 6088 KB Output is correct
6 Correct 29 ms 6112 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 226116 KB Output is correct
2 Correct 1025 ms 220060 KB Output is correct
3 Correct 1711 ms 349632 KB Output is correct
4 Correct 1650 ms 349572 KB Output is correct
5 Correct 855 ms 182908 KB Output is correct
6 Correct 848 ms 182780 KB Output is correct

Subtask #4
0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 4307 ms 888208 KB Output is correct
2 Correct 4077 ms 866604 KB Output is correct
3 Runtime error 4248 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -