| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1048718 |
2024-08-08T09:14:08 Z |
ksun69(#11093) |
Light Bulbs (EGOI24_lightbulbs) |
C++17 |
|
45 ms |
1296 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(x_left * 5 < y_left){
state = 1;
d = y_left;
} else if(y_left * 5 < x_left){
state = 2;
d = x_left;
} else {
state = 0;
d = min(L, min(x_left, y_left));
}
assert(d > 0);
auto query = [&](vector<pair<int,int> > places) -> pair<int,int> {
if(places.size() == 1) return get_dir_next(places[0].first, places[0].second) == 'H' ? make_pair(1, 0) : make_pair(0, 1);
int f = (int)places.size();
vector<vector<int> > grid(N, vector<int>(N, 0));
for(auto [x, y] : places) grid[x][y] = 1;
if(state == 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;
}
}
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 = int(v > 0);
ny = (f - v);
} else if(state == 2){
nx = v;
ny = 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]});
}
}
bool done = false;
y_combinator(
[&](auto self, vector<pair<int,int> > places, pair<int,int> res) -> void {
if(done) return;
if(res.second == 0){
for(auto [x, y] : places){
found_dir[0][x] = y;
}
if(state == 1) done = true;
return;
}
if(res.first == 0){
for(auto [x, y] : places){
found_dir[1][y] = x;
}
if(state == 2) done = true;
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
| # |
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 |
1 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 |
1 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 |
1 ms |
344 KB |
Output is correct |
| 17 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
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 |
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 |
1 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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 24 |
Correct |
0 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
0 ms |
344 KB |
Output is correct |
| 27 |
Correct |
1 ms |
344 KB |
Output is correct |
| 28 |
Correct |
1 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
0 ms |
344 KB |
Output is correct |
| 31 |
Correct |
0 ms |
344 KB |
Output is correct |
| 32 |
Correct |
0 ms |
344 KB |
Output is correct |
| 33 |
Correct |
1 ms |
344 KB |
Output is correct |
| 34 |
Correct |
0 ms |
344 KB |
Output is correct |
| 35 |
Correct |
0 ms |
344 KB |
Output is correct |
| 36 |
Correct |
0 ms |
344 KB |
Output is correct |
| 37 |
Correct |
0 ms |
344 KB |
Output is correct |
| 38 |
Correct |
0 ms |
344 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
0 ms |
344 KB |
Output is correct |
| 41 |
Correct |
0 ms |
344 KB |
Output is correct |
| 42 |
Correct |
0 ms |
344 KB |
Output is correct |
| 43 |
Correct |
0 ms |
344 KB |
Output is correct |
| 44 |
Correct |
0 ms |
344 KB |
Output is correct |
| 45 |
Correct |
1 ms |
344 KB |
Output is correct |
| 46 |
Correct |
0 ms |
344 KB |
Output is correct |
| 47 |
Correct |
0 ms |
344 KB |
Output is correct |
| 48 |
Correct |
0 ms |
344 KB |
Output is correct |
| 49 |
Correct |
0 ms |
344 KB |
Output is correct |
| 50 |
Correct |
0 ms |
344 KB |
Output is correct |
| 51 |
Correct |
0 ms |
344 KB |
Output is correct |
| 52 |
Correct |
0 ms |
344 KB |
Output is correct |
| 53 |
Correct |
0 ms |
344 KB |
Output is correct |
| 54 |
Correct |
0 ms |
344 KB |
Output is correct |
| 55 |
Correct |
0 ms |
344 KB |
Output is correct |
| 56 |
Correct |
0 ms |
344 KB |
Output is correct |
| 57 |
Correct |
1 ms |
344 KB |
Output is correct |
| 58 |
Correct |
0 ms |
344 KB |
Output is correct |
| 59 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
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 |
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 |
1 ms |
352 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 |
Correct |
0 ms |
344 KB |
Output is correct |
| 24 |
Correct |
0 ms |
344 KB |
Output is correct |
| 25 |
Correct |
0 ms |
344 KB |
Output is correct |
| 26 |
Correct |
0 ms |
344 KB |
Output is correct |
| 27 |
Correct |
0 ms |
344 KB |
Output is correct |
| 28 |
Correct |
0 ms |
344 KB |
Output is correct |
| 29 |
Correct |
0 ms |
344 KB |
Output is correct |
| 30 |
Correct |
1 ms |
344 KB |
Output is correct |
| 31 |
Correct |
0 ms |
344 KB |
Output is correct |
| 32 |
Correct |
1 ms |
344 KB |
Output is correct |
| 33 |
Correct |
0 ms |
344 KB |
Output is correct |
| 34 |
Correct |
0 ms |
344 KB |
Output is correct |
| 35 |
Correct |
1 ms |
344 KB |
Output is correct |
| 36 |
Correct |
0 ms |
352 KB |
Output is correct |
| 37 |
Correct |
0 ms |
344 KB |
Output is correct |
| 38 |
Correct |
1 ms |
344 KB |
Output is correct |
| 39 |
Correct |
0 ms |
348 KB |
Output is correct |
| 40 |
Correct |
0 ms |
352 KB |
Output is correct |
| 41 |
Correct |
0 ms |
352 KB |
Output is correct |
| 42 |
Correct |
1 ms |
352 KB |
Output is correct |
| 43 |
Correct |
0 ms |
352 KB |
Output is correct |
| 44 |
Correct |
0 ms |
352 KB |
Output is correct |
| 45 |
Correct |
0 ms |
352 KB |
Output is correct |
| 46 |
Correct |
0 ms |
344 KB |
Output is correct |
| 47 |
Correct |
0 ms |
344 KB |
Output is correct |
| 48 |
Correct |
0 ms |
344 KB |
Output is correct |
| 49 |
Correct |
0 ms |
344 KB |
Output is correct |
| 50 |
Correct |
0 ms |
344 KB |
Output is correct |
| 51 |
Correct |
0 ms |
344 KB |
Output is correct |
| 52 |
Correct |
0 ms |
344 KB |
Output is correct |
| 53 |
Correct |
0 ms |
344 KB |
Output is correct |
| 54 |
Correct |
0 ms |
344 KB |
Output is correct |
| 55 |
Correct |
0 ms |
344 KB |
Output is correct |
| 56 |
Correct |
0 ms |
344 KB |
Output is correct |
| 57 |
Correct |
0 ms |
344 KB |
Output is correct |
| 58 |
Correct |
0 ms |
344 KB |
Output is correct |
| 59 |
Correct |
3 ms |
344 KB |
Output is correct |
| 60 |
Correct |
3 ms |
344 KB |
Output is correct |
| 61 |
Correct |
19 ms |
560 KB |
Output is correct |
| 62 |
Partially correct |
24 ms |
552 KB |
Partially correct |
| 63 |
Partially correct |
44 ms |
556 KB |
Partially correct |
| 64 |
Partially correct |
45 ms |
560 KB |
Partially correct |
| 65 |
Partially correct |
33 ms |
552 KB |
Partially correct |
| 66 |
Partially correct |
36 ms |
552 KB |
Partially correct |
| 67 |
Partially correct |
32 ms |
552 KB |
Partially correct |
| 68 |
Partially correct |
41 ms |
548 KB |
Partially correct |
| 69 |
Partially correct |
23 ms |
552 KB |
Partially correct |
| 70 |
Partially correct |
43 ms |
556 KB |
Partially correct |
| 71 |
Correct |
16 ms |
548 KB |
Output is correct |
| 72 |
Correct |
6 ms |
548 KB |
Output is correct |
| 73 |
Correct |
4 ms |
548 KB |
Output is correct |
| 74 |
Correct |
7 ms |
548 KB |
Output is correct |
| 75 |
Correct |
9 ms |
548 KB |
Output is correct |
| 76 |
Correct |
7 ms |
548 KB |
Output is correct |
| 77 |
Correct |
4 ms |
552 KB |
Output is correct |
| 78 |
Correct |
16 ms |
556 KB |
Output is correct |
| 79 |
Partially correct |
22 ms |
560 KB |
Partially correct |
| 80 |
Correct |
7 ms |
552 KB |
Output is correct |
| 81 |
Partially correct |
38 ms |
556 KB |
Partially correct |
| 82 |
Partially correct |
34 ms |
548 KB |
Partially correct |
| 83 |
Partially correct |
36 ms |
552 KB |
Partially correct |
| 84 |
Partially correct |
40 ms |
1296 KB |
Partially correct |
| 85 |
Partially correct |
36 ms |
556 KB |
Partially correct |
| 86 |
Correct |
4 ms |
548 KB |
Output is correct |
| 87 |
Correct |
6 ms |
552 KB |
Output is correct |
| 88 |
Correct |
3 ms |
344 KB |
Output is correct |
| 89 |
Correct |
5 ms |
552 KB |
Output is correct |
| 90 |
Correct |
8 ms |
548 KB |
Output is correct |
| 91 |
Correct |
5 ms |
544 KB |
Output is correct |
| 92 |
Partially correct |
41 ms |
552 KB |
Partially correct |
| 93 |
Partially correct |
32 ms |
800 KB |
Partially correct |
| 94 |
Partially correct |
33 ms |
556 KB |
Partially correct |
| 95 |
Partially correct |
33 ms |
556 KB |
Partially correct |
| 96 |
Partially correct |
42 ms |
556 KB |
Partially correct |
| 97 |
Correct |
1 ms |
344 KB |
Output is correct |
