oj.uz

Submission #1048637

# Submission time Handle Problem Language Result Execution time Memory
1048637 2024-08-08T08:53:27 Z ksun69(#11093) Light Bulbs (EGOI24_lightbulbs) C++17
0 / 100
 1 ms 344 KB 
#include <bits/stdc++.h>
using namespace std;

// C. Light Bulbs
// Problem Name lightbulbs
// Time Limit 4 seconds
// Memory Limit 1 gigabyte
// Shortly after founding his lightbulb company in Eindhoven in 1891, Frederik Philips made a great
// discovery: lightbulbs that light up an infinite ray in the horizontal or vertical direction. With this
// new discovery, he wants to revolutionize the interior design of modern homes.
// He plans an elaborate installation with his son, Gerard. They install N lamps in an N × N grid in
// a room. They want to light up the whole room with as few lamps turned on as possible to save
// electricity. Each lamp is either vertical, meaning it lights up all squares in its column, or horizontal,
// meaning it lights up all squares in its row.
// The illustration below shows an example of a vertical (left) and a horizontal (right) lamp.
// Unfortunately, they did not pay attention when installing the lamps and do not remember which
// lamps light up horizontally or vertically. Instead, they conduct some experiments to figure out
// which lamps to use to light up the whole room. Gerard stays in the room with the lamps, while
// Frederik operates the switches from another room.
// In each experiment, Frederik turns each lamp on or off and Gerard reports how many squares are
// lit up in total; a square that is lit up by two or more separate lamps is only counted once. It does
// not matter how many lamps are turned on during the experiments, but they are in a rush and
// ideally want to conduct as few experiments as possible.
// 2
// lightbulbs (1 of 5) 
// Help them find an arrangement of lamps that lights up the whole room and uses the fewest lamps.
// They can conduct at most 2 000 experiments. However, you will get a higher score if they use fewer
// experiments.
// Interaction
// This is an interactive problem.
// Your program should start by reading a line with an integer N, the height and width of the
// grid.
// Then, your program should interact with the grader. To conduct an experiment, you should
// first print a line with a question mark “?”. On the next N lines, output an N × N grid
// specifying which lamps are lit. Specifically, on each of these lines, output a string of length
// N, consisting of 0's (turned off) and 1's (turned on). Then, your program should read a single
// integer ℓ (0 ≤ ℓ ≤ N ), the number of grid squares lit up by turning on the lamps specified.
// When you want to answer, print a line with an exclamation mark “!”, followed by N lines
// with the grid in the same format as above. In order for your answer to be accepted, the
// lamps must light up the whole grid and the number of turned-on lamps must be the
// fewest possible.
// After this, your program should exit.
// The grader is non-adaptive, meaning that the grid of lamps is determined before the interaction
// begins.
// Make sure to flush standard output after issuing each experiment; otherwise, your program might
// get judged as “Time Limit Exceeded”. In Python, this happens automatically as long as you use
// input() to read lines. In C++, cout << endl; flushes in addition to printing a newline; if using
// printf, use fflush(stdout).
// Constraints and Scoring
// 3 ≤ N ≤ 100.
// You can issue at most 2 000 experiments (printing the final answer does not count as an
// experiment). If you exceed this, you will get the verdict “Wrong Answer”.
// Your solution will be tested on a set of test groups, each worth a number of points. Each test group
// contains a set of test cases. To get the points for a test group, you need to solve all test cases in the
// test group.

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N;
	cin >> N;
	auto ask = [&](vector<vector<int>> grid){
		cout << "?" << '\n';
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++) cout << grid[i][j];
			cout << '\n';
		}
		cout << flush;
		int ans;
		cin >> ans;
		return ans;
	};

	auto answer = [&](vector<pair<int, int>> ans){
		vector<vector<int>> grid(N, vector<int>(N, 0));
		for(auto [x, y] : ans){
			grid[x][y] = 1;
		}
		cout << "!" << '\n';
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++) cout << grid[i][j];
			cout << '\n';
		}
		cout << flush;
	};

	auto not_a = [&](int a){
		vector<int> y;
		for(int i = 0; i < N; i++) if(i != a) y.push_back(i);
		return y;
	};

	auto count_row = [&](int dir, int x, vector<int> y) -> int {
		assert(y.size() > 1);
		vector<vector<int>> grid(N, vector<int>(N, 0));
		int c = (int)y.size();
		for(int i : y){
			(dir ? grid[i][x] : grid[x][i]) = 1;
		}
		int v = ask(grid);
		if(v == c * N) return c;
		assert((v - N) % (N-1) == 0);
		return (v - N) / (N-1);
	};

	vector<int> id;
	for(int i = 0; i < N; i++) id.push_back(i);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	auto get_dir_init = [&](int x, int y){
		int val = count_row(0, x, id) - count_row(0, x, not_a(y));
		if(val == 1) return 'V';
		return 'H';
	};
	char dir_0 = get_dir_init(0, 0);
	auto get_dir_next = [&](int x, int y) -> char {
		vector<vector<int> > grid(N, vector<int>(N, 0));
		grid[0][0] = 1;
		grid[x][y] = 1;
		int val = ask(grid);
		if(val == N || val == 2*N) return dir_0;
		return dir_0 == 'V' ? 'H' : 'V';
	};
	vector<vector<int> > found_dir(2, vector<int>(N, -1));
	while(true){
		vector<int> done_x, done_y;
		for(int i = 0; i < N; i++) if(found_dir[0][i] != -1) done_x.push_back(i);
		for(int i = 0; i < N; i++) if(found_dir[1][i] != -1) done_y.push_back(i);
		vector<int> left_x, left_y;
		for(int i = 0; i < N; i++) if(found_dir[0][i] == -1) left_x.push_back(i);
		for(int i = 0; i < N; i++) if(found_dir[1][i] == -1) left_y.push_back(i);
		shuffle(left_x.begin(), left_x.end(), rng);
		shuffle(left_y.begin(), left_y.end(), rng);
		int cx = (int)done_x.size();
		int cy = (int)done_y.size();
		if(cx == N || cy == N) break;
		int higher_dir = (cx > cy ? 0 : 1);
		int x_left = N - cx;
		int y_left = N - cy;
		int L = max(cx, cy);
		if(L == 0){
			char dir = get_dir_next(left_x[0], left_y[0]);
			if(dir == 'H'){
				found_dir[0][left_x[0]] = left_y[0];
			} else {
				found_dir[1][left_y[0]] = left_x[0];
			}
			continue;
		}
		int d;
		int state = 0;
		if(L <= min(x_left, y_left) || (x_left * 2 >= y_left && y_left * 2 >= x_left)){
			state = 0;
			d = min(L, min(x_left, y_left));
		} else if(x_left * 2 < y_left){
			state = 1;
			d = min(L, y_left);
		} else if(y_left * 2 < x_left){
			state = 2;
			d = min(L, x_left);
		} else assert(false);
		assert(d > 0);
		auto query = [&](vector<pair<int,int> > places) -> pair<int,int> {
			int f = (int)places.size();
			vector<vector<int> > grid(N, vector<int>(N, 0));
			if(higher_dir == 0){
				for(int x : done_x) grid[x][found_dir[0][x]] = 1;
			} else {
				for(int y : done_y) grid[found_dir[1][y]][y] = 1;
			}
			for(auto [x, y] : places) grid[x][y] = 1;
			int res = ask(grid);
			int sx = higher_dir == 0 ? cx : 0;
			int sy = higher_dir == 1 ? cy : 0;
			for(int v = 0; v <= f; v++){
				int nx, ny;
				if(state == 0){
					nx = sx + v;
					ny = sy + (f - v);
				} else if(state == 1){
					nx = sx + int(v > 0);
					ny = sy + (f - v);
				} else if(state == 2){
					nx = sx + v;
					ny = sy + int((f-v) > 0);
				} else assert(false);
				int val = N*N - (N - nx) * (N - ny);
				if(val == res) return {v, f-v};
			}
			assert(false);
		};
		vector<pair<int,int> > places_init;
		if(state == 0){
			for(int i = 0; i < d; i++){
				places_init.push_back({left_x[i], left_y[i]});
			}
		} else if(state == 1){
			for(int i = 0; i < d; i++){
				places_init.push_back({left_x[0], left_y[i]});
			}
		} else if(state == 2){
			for(int i = 0; i < d; i++){
				places_init.push_back({left_x[i], left_y[0]});
			}
		}
		y_combinator(
			[&](auto self, vector<pair<int,int> > places, pair<int,int> res) -> void {
				if(res.second == 0){
					for(auto [x, y] : places){
						found_dir[0][x] = y;
					}
					return;
				}
				if(res.first == 0){
					for(auto [x, y] : places){
						found_dir[1][y] = x;
					}
					return;
				}
				int m = (int)places.size() / 2;
				vector<pair<int,int> > places_l(places.begin(), places.begin() + m);
				vector<pair<int,int> > places_r(places.begin() + m, places.end());
				pair<int,int> res_l = query(places_l);
				pair<int,int> res_r = {res.first - res_l.first, res.second - res_l.second};
				self(places_l, res_l);
				self(places_r, res_r);
			}
		)(places_init, query(places_init));
	}
	vector<int> done_x, done_y;
	for(int i = 0; i < N; i++) if(found_dir[0][i] != -1) done_x.push_back(i);
	for(int i = 0; i < N; i++) if(found_dir[1][i] != -1) done_y.push_back(i);
	int cx = (int)done_x.size();
	int cy = (int)done_y.size();
	vector<pair<int, int>> ans;
	if(cx == N){
		for(int i = 0; i < N; i++){
			if(found_dir[0][i] != -1) ans.push_back({i, found_dir[0][i]});
		}
	} else if(cy == N){
		for(int i = 0; i < N; i++){
			if(found_dir[1][i] != -1) ans.push_back({found_dir[1][i], i});
		}
	} else assert(false);
	answer(ans);
}

// python3 testing_tool.py ./C < sample1.in

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Incorrect 0 ms 344 KB The lamps do not light up the entire grid
14 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 344 KB The lamps do not light up the entire grid
8 Halted 0 ms 0 KB -

Subtask #3
0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Incorrect 0 ms 344 KB The lamps do not light up the entire grid
24 Halted 0 ms 0 KB -