Submission #1048351

# Submission time Handle Problem Language Result Execution time Memory
1048351 2024-08-08T07:01:32 Z ksun69(#11093) Make them Meet (EGOI24_makethemmeet) C++17
0 / 100
261 ms 24580 KB
#include <bits/stdc++.h>
using namespace std;

// D. Make Them Meet
// Problem Name makethemmeet
// Time Limit 9 seconds
// Memory Limit 1 gigabyte
// Mila and Laura have been friends online for a long time; they have never met in real life. Currently,
// they are both attending the same onsite event, which means that they will surely meet. However,
// the hotel where they both are staying is very big and confusing. Therefore, after several days, they
// still have not run into each other.
// The hotel consists of N rooms, numbered 0 to N − 1. Each room has a lamp that can be changed
// into different colours. You have found the electrical service room of the hotel, allowing you to alter
// the colours of the lamps. Your goal is to guide Mila and Laura using the lamps to finally make them
// meet.
// The hotel can be represented as a graph with N vertices (the rooms) and M edges (the corridors
// connecting the rooms). Mila and Laura initially start in two different rooms but you do not know
// which ones. You can make a number of moves. Each move consists of printing a list of N integers,
// c , c ,..., c , meaning that the colour of the lamp in room i becomes c for every
// i = 0, 1,..., N − 1. Mila and Laura will then look at the colour of the lamp in the room they are
// currently in and walk to a neighbouring room whose lamp has the same colour. If there is no such
// neighbouring room, they will stay where they are. If there are several such neighbouring rooms,
// they will choose one arbitrarily.
// If Mila and Laura are in the same room or use the same corridor simultaneously at any point
// during your moves, you have succeeded in making them meet. You can make at most 20 000
// moves, but you will get a higher score if you use fewer moves.
// Note that you do not know which rooms Mila and Laura start in or how they walk if they have
// multiple rooms with the same colour to choose from. Your solution must be correct regardless
// of their starting rooms or how they walk.
// Input
// 0 1 N−1 i
// makethemmeet (1 of 4) 
// The first line contains two integers, N and M, the number of rooms and the number of corridors
// in the hotel respectively.
// The following M lines each contain two integers, u and v , meaning that rooms u and v are
// connected by a corridor.
// Output
// Print one line with an integer K, the number of moves.
// On each of the following K lines, print N integers, c , c ,..., c , such that 0 ≤ c ≤ N for all i.
// These K lines represent your moves in the chronological order.
// Constraints and Scoring
// 2 ≤ N ≤ 100.
// N − 1 ≤ M ≤ .
// 0 ≤ u , v ≤ N − 1, and u ≠ v .
// You can reach every room from every other room. Furthermore, there are no corridors going
// from a room to itself, and there are not multiple corridors between any pair of rooms.
// You may use at most 20 000 moves (that is, K ≤ 20 000).
// 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.

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, M;
	cin >> N >> M;
	vector<vector<int> > adj(N);
	vector<pair<int, int> > edges;
	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		edges.push_back({u, v});
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	vector<vector<int> > state(N, vector<int>(N, 1));

	for(int i = 0; i < N; i++){ state[i][i] = 0; }

	vector<vector<int> > queries;
	while(true){
		int e = rng() % M;
		auto [u, v] = edges[e];
		vector<int> c(N, 0);
		c[u] = 1;
		c[v] = 1;
		queries.push_back(c);
		for(int i = 0; i < N; i++){
			if(i == u || i == v) continue;
			swap(state[i][u], state[i][v]);
			swap(state[u][i], state[v][i]);
		}
		state[u][v] = state[v][u] = state[u][u] = state[v][v] = 0;
		if(state == vector<vector<int> >(N, vector<int>(N, 0))){
			break;
		}
	}
	cout << queries.size() << '\n';
	for(auto c : queries){
		for(int i = 0; i < N; i++){
			cout << c[i] << " \n"[i == N-1];
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 261 ms 24580 KB Number of moves out of bounds: 38570
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB If people start at 0 and 1, then they can avoid each other
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB If people start at 1 and 2, then they can avoid each other
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 261 ms 24580 KB Number of moves out of bounds: 38570
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 261 ms 24580 KB Number of moves out of bounds: 38570
5 Halted 0 ms 0 KB -