305615: CF1063E. Lasers and Mirrors

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Lasers and Mirrors

题意翻译

有一个 $n\times n$ 的房间,房间下方有 $n$ 个发射激光的发射器,上方有 $n$ 个接收器分别对应一个不同的发射器。 现在给你每个发射器对应的接收器的编号,请你在房间里放上一些镜子,使得有最多的接收器收到对应发射器的信号。要求输出最多可能收到对应信号的接收器数目,并且输出此时房间对应的布局。其中 `.` 表示空地,`/`,`\` 分别表示不同朝向的镜子。(可以结合题图理解)允许接收器接收非对应发射器的信号,但这种情况不计入答案。多种答案输出一种即可。 $n \leq 1000$。

题目描述

Oleg came to see the maze of mirrors. The maze is a $ n $ by $ n $ room in which each cell is either empty or contains a mirror connecting opposite corners of this cell. Mirrors in this maze reflect light in a perfect way, which causes the interesting visual effects and contributes to the loss of orientation in the maze. Oleg is a person of curious nature, so he decided to install $ n $ lasers facing internal of the maze on the south wall of the maze. On the north wall of the maze, Oleg installed $ n $ receivers, also facing internal of the maze. Let's number lasers and receivers from west to east with distinct integers from $ 1 $ to $ n $ . Each laser sends a beam of some specific kind and receiver with number $ a_i $ should receive the beam sent from laser number $ i $ . Since two lasers' beams can't come to the same receiver, these numbers form a permutation — each of the receiver numbers occurs exactly once. You came to the maze together with Oleg. Help him to place the mirrors in the initially empty maze so that the maximum number of lasers' beams will come to the receivers they should. There are no mirrors outside the maze, so if the laser beam leaves the maze, it will not be able to go back.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 1 \le n \le 1000 $ ) — the size of the maze. The second line contains a permutation of $ n $ integers $ a_i $ ( $ 1 \le a_i \le n $ ), where $ a_i $ defines the number of the receiver, to which the beam from $ i $ -th laser should come.

输出格式


In the first line print the maximum possible number of laser beams, which can come to the receivers they should. In the next $ n $ lines of length $ n $ print the arrangement of mirrors, causing such number of laser beams to come where they should. If the corresponding cell is empty, print ".", otherwise print "/" or "\\", depending on the orientation of the mirror. In your output north should be above, south should be below, and west and east should be on left and on the right respectively. It is allowed for laser beams to come not to the receivers they correspond to, but they are not counted in the answer. If there are multiple arrangements of mirrors leading to the optimal answer — print any of them.

输入输出样例

输入样例 #1

4
4 1 3 2

输出样例 #1

3
.\..
\\..
/../
...\

说明

The picture illustrates the arrangements of the mirrors in the first example. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1063E/19ee8b9d2f31cec8a8e7ae55db512ff2fc59d36c.png)

Input

题意翻译

有一个 $n\times n$ 的房间,房间下方有 $n$ 个发射激光的发射器,上方有 $n$ 个接收器分别对应一个不同的发射器。 现在给你每个发射器对应的接收器的编号,请你在房间里放上一些镜子,使得有最多的接收器收到对应发射器的信号。要求输出最多可能收到对应信号的接收器数目,并且输出此时房间对应的布局。其中 `.` 表示空地,`/`,`\` 分别表示不同朝向的镜子。(可以结合题图理解)允许接收器接收非对应发射器的信号,但这种情况不计入答案。多种答案输出一种即可。 $n \leq 1000$。

加入题单

上一题 下一题 算法标签: