QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #502408 | #9156. 百万富翁 | fryan | 71.00004 | 2060ms | 99616kb | C++14 | 23.6kb | 2024-08-03 05:06:11 | 2024-08-03 05:06:11 |
Judging History
answer
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠉⠻⢿⣋⣥⣴⣶⣿⣿⣿⡿⠿⠿⠿⠿⠿⠿⠿⢶⣶⣤⣀⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣦⠬⠉⠛⠉⠉⠀⠀⠀⠀⠀⠀⠀⣀⣠⣴⣦⣤⣄⣉⡛⠷⣮⣟⡁⠈⠉⠻⢯⣟⡻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠛⠛⠛⣛⡻⠟⠋⢁⣠⣤⠾⠛⠁⠀⢀⡤⢆⣠⣴⣾⣿⠿⠿⠛⠛⢛⡟⣻⣻⡙⢿⣟⠿⡿⣿⣦⣄⣈⠻⣷⡷⣮⣙⠿⣿⣿⣿⠟⠋⠉⠁⠀⠀⣠⣴⡶⣿⣿⣿⢿⡿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣣⣶⣶⣶⡦⠚⠉⣀⣴⣾⠟⠋⠀⠀⠀⣠⠶⠋⢰⣯⡾⠛⣉⡠⠄⠒⢀⣬⠷⣋⢥⡑⢎⠲⡹⣯⡱⣍⠻⣿⣿⣿⣮⡹⣯⡟⣷⣌⠙⢿⣦⠀⠢⡠⣔⠛⢉⣥⣿⣛⡷⣹⣮⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣜⣯⠞⠁⣀⣴⣾⠿⠋⠀⠀⠀⠀⣠⠞⠁⢀⣴⠟⣁⡒⠍⢀⢠⣄⣶⠛⡑⣊⠔⢢⡙⢬⡓⢥⠻⣷⡌⡗⢦⡹⢿⣞⣷⢩⡟⣼⣛⣷⡄⠙⢷⣀⠐⣠⣶⠿⣛⡶⣫⣾⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⡿⠁⣠⣞⣿⠟⡁⠀⠀⠀⠀⣠⠀⠉⠃⣠⠞⡥⠒⠄⢈⣤⢾⣻⠟⢁⠜⡰⠉⡜⠠⠖⣂⠹⠆⡍⣿⡎⡝⣣⡕⣫⢻⡞⡧⡞⡩⢿⡎⣿⣆⠀⠹⣾⠋⢱⡿⣏⣿⣿⣿⣿⣿⣻⣿⣿⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⢁⣴⣿⠟⣡⠎⠀⠀⠀⢀⡞⠁⠤⢀⡼⠋⠀⠀⣠⠾⠛⢡⡾⢁⠰⡈⢆⢡⢃⠬⣉⠜⣄⠣⣩⠐⣿⡗⡘⣆⠹⣼⡱⣿⡡⢇⡛⣼⢿⡜⣿⣆⠀⠘⣿⣿⣻⣿⣿⣿⢿⣳⣯⣿⣿⡿⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⣾⠟⢁⡴⠁⠀⠀⠀⣰⠏⠀⠀⣠⠟⠀⠀⣰⠞⠁⠀⣴⠟⠀⠄⢂⠑⣂⢆⢒⡐⣒⢊⣷⣐⣴⠡⢫⣷⠑⡬⢑⡸⡇⢹⣷⠱⠞⠁⠀⣷⢹⣿⡄⣧⡘⣿⣿⡿⣯⣟⣯⣿⡾⣿⢯⣿⢳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⣃⣴⡟⠀⠀⠀⢀⡾⠁⡈⠀⣰⠏⠀⣠⠞⠁⡀⢀⣾⠋⠀⠀⡈⣧⠔⢀⠊⡤⠘⡬⣸⡿⡟⠁⠀⣿⡿⡀⠳⠀⢸⣧⠸⣿⡇⢠⢂⠳⡸⣎⣿⡇⣽⣷⡘⣿⣿⣿⣿⣿⣷⣻⡟⣿⢳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢏⣲⣿⠟⠀⠀⢠⢣⣟⠃⡸⠀⣰⠏⢀⡾⠉⠀⠜⢃⡾⠁⠂⠀⣼⣿⠇⣀⠂⡜⠠⣯⢁⣿⠓⠁⠀⢸⣿⣷⡕⡨⣡⠂⣽⣦⢹⣷⡏⢬⡓⣥⢋⣽⣿⢼⣿⣿⢹⣿⣿⣿⣿⣿⣿⣿⣷⣿⡻⢿⣿⠻⠿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⡿⠃⣼⣿⡟⠀⠀⠀⢢⠟⡜⢰⠃⣰⠏⣠⠟⠁⣀⠚⢀⡿⠁⡐⢀⡿⣿⠃⡐⣀⠣⡐⢣⠗⣾⡏⠤⣴⠀⣾⡿⣟⣧⡑⣡⠚⠤⡟⣾⡇⣏⢆⡓⡆⡧⢺⣿⣾⣯⣷⢛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣽⢷⣄⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢋⣵⣿⣿⣿⠃⣾⣿⢻⠀⠀⠀⢠⡟⢰⠇⡟⢠⡟⣰⠯⠀⠆⠠⢀⣿⠁⣰⠁⣼⣿⠟⣀⠒⠄⡡⠰⣍⣿⡟⢌⠒⡤⣹⡿⠁⣿⢿⡀⠧⡜⢒⡯⢼⡗⣽⢨⠼⡑⣎⢳⣿⣽⡷⣿⢢⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣴⣿⣿⣿⣿⠇⣼⣿⠃⡏⠀⠀⢀⡾⢀⡞⢰⠃⣾⣳⣿⠁⡘⢀⣡⣿⠇⣰⠇⣸⢻⡏⠠⠰⡁⠌⢡⢃⣾⣿⡁⢮⢂⣾⡿⠁⠀⢹⡞⡏⡞⡸⠤⣟⢾⡏⣿⢠⢻⡱⣌⣻⣿⢼⡿⣽⣚⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢰⡿⠃⣰⠃⠀⠀⣸⠇⣾⡇⢾⣹⢷⣿⠇⠀⣤⡾⢋⣿⡾⠃⣼⢏⣿⠁⣊⠔⠡⣼⠗⣦⣿⠃⢼⣲⣿⠏⠀⠀⠀⠀⣿⣕⡱⣃⢣⡿⣿⢃⣿⢌⡳⣚⡾⣼⣿⢻⡿⣽⣣⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣀⠀⠀⠈⢻⣿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡷⠟⠃⣼⣿⡀⠀⢀⡿⢰⢻⠀⣿⣿⣟⡟⣠⠞⣋⣠⣼⠏⢡⣼⡟⣼⢃⠰⠤⣈⡿⢋⣼⣿⡏⢌⣴⣿⠥⡤⣤⣤⣀⣀⣸⡇⠳⣇⢮⣿⡿⢌⡟⡬⢇⣿⢷⣿⣏⣿⡽⣾⢵⣿⣿⣿⣿⣿⣿⠿⠿⠿⠛⠛⠛⣇⠘⣶⣄⠀⠀⠙⢿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠂⣼⠿⣿⡇⠀⣸⠃⣏⣾⢸⣿⣿⣿⣷⠟⠛⢋⣿⣁⣶⠛⢹⢇⡟⠠⠌⣰⣿⣵⠿⢫⡏⣴⡾⠋⠀⠀⠀⠀⠀⠀⠈⠉⢿⡱⠸⣼⣿⡏⣼⡧⢹⢮⣟⣾⣿⣘⣿⡽⣳⣾⣿⠿⣟⣯⠉⠀⠀⠠⣤⣀⠀⢀⣾⡄⢰⡈⠳⣄⠀⠈⢻⡝⢿⣿
⣿⣳⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⡾⣼⡿⣸⡏⡇⠀⡿⠀⡏⣿⢸⣿⣿⡟⠁⢀⣴⡿⠛⠉⠀⠀⡞⢸⠇⣐⣾⣿⠟⠁⣰⣿⠿⠋⢀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠈⣷⣣⣿⣿⢡⣿⡘⢧⣿⢣⣿⢣⣾⣯⣿⡟⠉⣠⣶⣿⡟⠀⠀⠀⠀⠀⠈⢻⣿⣿⣷⠀⢇⠀⠈⠳⠀⠀⠙⣆⠉
⣿⣽⣻⣟⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⠀⣸⣽⢿⣇⡿⡇⢡⠀⡧⠀⣧⣿⢸⣿⡿⠀⢶⣏⡀⠀⠠⠤⡀⠀⡏⢾⣡⡾⠛⠀⣠⠾⠛⠁⠀⢀⣠⣧⣿⣿⣾⣶⣷⣟⣀⠀⣀⣸⣿⣿⡟⣸⢧⢹⢯⣭⣿⢝⣾⡿⣯⣿⣿⣾⣿⣿⣯⣤⣤⣤⣤⣀⡀⠐⠺⠿⣿⣿⡆⢸⡄⠰⠄⠈⠂⠀⠈⢷
⣿⣿⣿⣿⣿⣿⣾⣯⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣻⣽⣿⠏⠀⣰⢿⠇⣾⢸⣷⣧⢸⣤⣇⠀⣿⣿⣸⣿⣿⣶⣿⣿⣿⣿⣿⣶⣄⡀⡇⣹⡟⠁⠀⠊⠁⠀⠀⢀⣴⣿⠟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣄⣹⡟⢠⡟⣦⢿⣙⣾⣷⣿⣿⣿⠿⡿⣟⠛⣿⠛⠛⢿⣿⣿⣿⣿⣿⠗⠀⠀⠀⣿⣷⠘⡇⢈⠡⢂⠀⠀⠀⠀
⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⣞⢻⣏⢿⡶⣽⣾⢿⣾⣯⣷⣿⣿⣿⣿⣿⠏⠀⣰⣿⡟⢈⡟⢸⣿⣿⠀⢿⣿⠀⣿⣿⣇⣿⣿⡿⠛⢁⣾⠟⣿⢿⣿⣷⣿⡟⠀⠀⠀⠀⠀⠀⠀⠚⠋⠀⢸⣿⣤⣿⢏⣿⡿⣿⢙⣿⣿⢿⡿⠁⡼⢸⢇⣿⣾⣿⣷⣿⣶⣿⣿⣿⣦⣧⣽⡅⠄⣼⣿⣿⣿⠟⠁⠀⠀⠀⠛⠉⠛⣷⡇⢐⢂⠐⡈⠤⠀⠀
⣄⣉⠛⡋⠏⢭⡉⢖⡁⢎⣍⣳⣬⣳⣾⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⠀⣰⣿⠙⢀⣻⠇⣼⣿⢻⡆⠘⣿⡆⢿⡭⢿⣿⣿⣇⠀⠘⣿⡞⣿⣾⡟⣿⠽⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⣿⠋⠻⣷⠟⢀⡽⣸⠏⢁⡟⠀⣠⣽⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣁⣴⡿⢰⢛⣿⣿⡛⠀⠀⠀⠀⠀⠀⠀⣀⣠⡟⣷⣆⠦⠁⠒⠨⠀⠂
⠉⠛⠛⠛⠿⠳⠟⠻⠛⠟⠛⠛⠻⠿⠿⢿⣿⡿⠿⠛⠛⠉⢉⠛⠻⠿⣿⠁⢰⣿⡏⡄⡬⣿⠀⣿⣿⡹⣽⡄⠙⣿⣾⡿⡽⣯⣇⠹⣦⠀⢿⣄⠈⢻⣷⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⢧⣤⣬⣤⡾⠝⠁⢠⣾⠶⠛⢯⣻⣟⣣⣶⣿⣿⣯⡛⠛⣿⣧⣸⣿⣿⣧⣸⢿⣿⣿⣿⠶⣤⣤⣤⣶⣾⣿⣿⣿⡇⣿⡿⣷⣯⣀⡁⠀⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠠⠀⠀⢀⣤⠔⠊⠁⠀⢀⣴⡇⢀⣿⣿⢃⢡⢹⣿⠀⢹⣿⢵⢫⡿⣄⠘⢷⣿⣵⣿⣿⠀⠊⠓⠖⠋⠙⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⣺⠏⠀⢀⣾⣷⡿⣿⣿⣿⣿⣿⣿⣿⣧⡉⢻⣿⣿⣿⣿⣿⡀⠀⣀⣠⣼⣿⣿⣿⣿⣿⣿⣿⣿⢧⣿⡿⣽⣿⣷⣦⡄⠀
⡐⠦⡄⡤⡄⣀⡀⢀⡀⣀⣀⣀⣁⣀⣤⣴⠶⠛⠉⠀⢀⣀⣴⡾⣟⣿⡇⢸⠿⣿⠀⢸⡆⢿⠀⢸⣿⡿⢋⡔⣩⣷⣌⠻⢿⣿⣿⡗⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⠁⣠⣶⣿⣿⣻⠿⠛⠉⠉⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣿⣿⣼⣿⣿⡷⣯⢿⣿⣿⣦
⣭⣷⣵⣶⣵⣦⣍⣲⣘⣴⡶⠴⠚⠋⠉⠀⢀⣠⣴⣾⣟⣿⡷⠟⠛⢹⡇⣼⣿⡟⠀⢸⡇⢾⡆⠀⣯⢐⣣⣾⣿⣿⣿⣷⣮⣽⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣯⠴⢚⣿⠞⣩⠞⢁⣀⣤⣤⣤⣤⣤⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⣻⢿⣯⣿
⠉⠉⠉⠉⠉⠁⠁⣀⣀⣀⣤⣤⠶⠶⠾⠿⠛⠛⠋⠉⠁⠀⣀⣤⣶⣿⡇⢼⣿⡇⠀⣽⡀⣿⢷⠀⢹⣾⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠊⠉⠁⠀⢀⣾⢃⣾⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣳⢿⣻⣿⣿
⣁⠉⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣠⣤⣴⣶⡿⣟⡹⢦⣫⣿⡸⣿⡇⠀⡿⣱⡏⣜⣧⡀⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⡿⠟⠛⠛⠛⠛⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⣿⣟⡿⣽⣯⣿
⠍⠛⠓⠲⠒⠲⠖⠶⠶⠶⠶⠶⠿⣟⣿⣿⣻⢟⡽⢯⣓⣳⠹⣭⣷⣿⡟⣷⣽⡇⠀⣧⣿⣿⣿⣻⣿⣮⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣶⣦⣄⢀⡤⠞⠉⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣡⢿⣹⢾⣿⣿⣻⣟⣾⢿
⣀⣩⠤⠓⠚⡉⢑⠌⠒⢁⣩⣴⣿⣿⡻⢶⣫⢏⡵⣓⢮⣼⣿⢻⡾⣏⣾⠟⣹⡇⠀⣿⣿⣟⣳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠲⢤⣴⣾⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣄⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣽⣾⡿⣿⣿⣿⣯⢿⡾⣿
⠀⠠⠠⠐⠃⢀⣠⣴⣾⡿⠿⣛⣯⠷⣛⣜⠶⣩⣶⣽⣿⢻⣼⣟⢳⣾⣵⣿⣿⣷⠀⢻⣿⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣰⠿⠛⠉⠀⠀⠀⠀⠈⠙⠻⢿⣿⣿⣿⣿⣇⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣿⣻⣽
⣠⠤⠴⠒⠛⠉⢉⣠⣤⡶⣟⢻⣬⢳⢣⣮⣷⣿⢟⣳⣾⣟⣳⣾⣿⣿⣿⣿⣿⡿⣧⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⠶⡾⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣯⣿⣿⣿⣿⣿⡷⣯⣟⣾
⣀⣀⠤⡴⡲⢞⣏⣳⢥⠻⣜⣣⣶⡻⣟⡻⣽⣼⣿⣛⣾⣾⣿⣿⣿⣿⣿⡿⣏⣳⣿⣦⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⣀⣀⡴⠶⠛⠉⣀⡾⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣟⣿⣿⣿⣿⡿⣽⢯⣿
⡝⣮⢳⢳⡝⣎⠾⡴⢯⡟⣿⣹⣶⣽⣾⡿⣟⣳⣷⣿⣿⣿⣿⣿⣿⡟⣧⣻⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣶⣶⣦⣴⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⣯⢿⣾
⣽⣲⣏⣷⣹⡮⢟⡹⢛⢫⣍⣥⣾⣟⣷⡟⠋⠁⢸⡿⣯⣹⣿⣿⣮⣽⣿⢿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⣿⣻⣞
⣿⣿⣿⣿⣿⣿⢷⣾⣳⢿⡿⢿⣛⠩⠄⢷⣀⣠⡿⢁⡤⠠⠄⠀⢀⣠⣴⣾⣿⡿⢿⢿⠻⢟⠿⣿⣻⣟⣾⣟⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⣿⣽⣯⣥⣥⣉⣙⣿⣿⣿⣿⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⣠⣾⣿⣿⣽⣯⣿⡿⣿⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⢇⣯⢷⣻
⣿⢿⣻⡽⣧⣻⣯⣶⡟⣿⣹⠷⣎⡟⣭⢢⡍⢭⡐⣌⡒⠉⣠⣴⣿⣿⣿⣿⣿⣿⢢⢍⠺⢭⣚⣯⣷⢯⣿⢾⣟⣾⣿⣿⣽⣿⣿⢿⣿⡿⣿⢯⡿⣽⢿⣻⢿⣿⢿⣟⣯⣿⣿⡿⠟⢹⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⠻⢿⣿⣿⣻⢷⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣷⣿⣿⣿⣿⣿⣿⣿⣿⢸⢮⡿⣼
⣿⣿⣷⣿⣿⣏⡘⢷⣿⣳⣯⣟⣽⣺⣵⣳⣮⠷⢚⣠⠶⣟⡿⣻⣟⣿⣿⣿⣿⣻⣇⢎⣏⢲⡿⣱⣿⣻⣽⣟⣿⣿⣻⣽⣿⢯⣿⡿⣯⡿⣯⢿⣹⣏⢿⣹⣟⣾⣿⣽⠟⠛⠉⠀⠀⢘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⡀⠀⠈⢿⡸⣿⣷⣿⣿⣿⣿⢿⡿⣿⣻⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣼⢧⣻⢟
⣿⣿⣟⣿⣯⣷⣹⠷⣮⣟⠛⠛⠛⠋⠉⣉⣠⣴⣿⣾⣿⣿⣷⣷⣟⡿⣫⣿⣿⣽⣿⡞⣨⡟⣼⣟⣷⣻⢷⣻⢿⡽⣯⣿⣾⢿⣯⣟⣷⢻⣭⣛⡶⣹⣿⣭⣉⣍⣁⣤⣤⣤⣲⣶⣶⣿⣿⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⣿⢦⣀⣾⠃⣼⣿⢿⣿⣿⣿⡟⢿⣟⣿⣿⡿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢣⢟⡶⣫⢏
⣿⣟⣿⣻⣽⣟⣿⢿⣻⣟⣻⣿⣿⣲⣷⣿⣿⣿⣿⣿⡿⣿⣿⣿⣿⣿⣟⡼⢿⣷⣻⣿⣷⣹⣟⣾⣳⢯⡿⣽⢯⣟⣷⡿⣽⣟⡾⠿⠚⠛⠋⠋⠙⠉⠉⠁⠀⠀⠀⠀⢨⣿⣿⣿⣿⣿⣿⣿⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⡻⣟⣦⢉⢷⣾⣿⣿⣿⣿⣿⣿⣾⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠾⣭⢞⡱⢮
⡟⡻⢟⡿⣯⣿⢾⡿⣿⣿⣿⣾⣿⣿⣿⣿⡿⣯⣟⣾⣟⡿⣞⡿⣿⣿⣿⡭⠽⡻⣷⣟⣿⣧⣛⡾⣭⡟⣽⣞⣻⢼⣯⣿⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣰⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⢀⣽⣯⣽⣤⡚⣿⣿⣿⣿⣿⣿⣿⣿⣿⡻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⢋⣵⠻⡜⣮⣝⣻
⡜⡥⢋⣞⡹⠊⢻⡝⣿⣞⣿⣻⣿⣿⢿⡧⣟⣷⣛⢾⣹⢻⡽⣻⣗⣿⣿⣿⣷⡷⣷⢿⣿⣿⣿⣿⣿⣿⣱⣻⢮⢷⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣶⣶⣿⢯⣼⡟⣱⣶⣿⡿⠻⣿⣳⡿⠃⠙⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡿⠟⠋⣁⣶⢿⢣⡻⣜⠾⣼⣻
⡦⣑⣡⢂⠱⢐⠣⡜⣥⡛⣾⣱⣿⣿⣿⡜⢧⡣⠽⠦⠙⠦⢓⡳⠾⣴⢭⣻⣷⣿⢾⣛⣯⣿⡿⣹⢾⣿⠳⣽⣺⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢨⣿⣿⣿⣿⠿⠛⠋⠁⠀⠀⢻⡿⠁⠀⢠⣿⣿⣦⡀⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⢘⡻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣛⠉⠀⢄⣳⡟⣏⢮⢣⡷⣭⣟⢷⣹
⣷⢯⣟⣾⣻⣞⢦⣰⡅⢋⡐⢿⣿⣻⢷⡸⣋⠁⠀⠀⠈⠀⠀⡱⣉⠧⣺⡯⡜⣿⣿⡿⣟⣯⠷⣏⢾⣟⠷⣤⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣾⣷⡾⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣦⡂⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⡇⢸⡇⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⢿⠋⢉⣠⣾⡟⢯⡜⣎⢮⢷⣹⠶⣯⢾⣽
⣿⢯⣟⣾⣳⢯⡿⣱⣟⢯⣿⣿⣿⣟⣳⣧⡇⠄⠀⠀⠀⠀⠀⠀⢂⣓⣿⡱⢭⣿⡿⣝⢯⡞⡽⣚⢬⠹⢷⣭⠏⠀⠀⡴⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣶⣶⣶⣿⣿⣿⣿⣿⣿⣿⡃⣼⡏⡜⣻⣿⣿⣿⣿⣿⣿⣿⡓⠦⡜⢢⣿⣶⡿⣏⡗⣞⣣⢾⡹⢯⣞⡷⣻⣭⣟⡾
⣟⡿⣞⣳⣽⢫⠾⣳⢯⣻⣿⣾⣿⣾⠏⠙⣿⣆⠀⡐⠀⠀⠀⡜⣤⣹⢧⢣⣿⡿⣝⡯⣞⡝⢶⠩⢆⣽⣾⡿⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⣤⣤⣶⠀⠀⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠠⣿⣿⡜⡽⣿⣿⣿⣿⣿⣿⣿⣿⢒⡍⣳⣿⢻⡵⣋⡾⣼⣣⢿⣽⣻⢾⣽⣷⣻⢎⡿
⣯⢟⡽⠣⠌⣉⣾⣿⡿⣷⣿⣿⣶⣿⣄⣸⣿⣿⡷⣧⣶⣦⣻⣜⡦⣿⡙⣶⣿⣻⡝⣾⢱⡚⣥⣿⠟⠁⠘⣷⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡤⠖⠒⠋⣉⣭⡽⣟⣫⣭⣿⣷⠀⠀⠀⠀⠀⠀⠉⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣘⣿⣿⣧⣛⣿⣿⣿⣿⣿⣏⢭⠣⣍⡒⣽⣯⢷⣻⡽⣽⣳⢯⣟⣾⣽⣿⣟⡷⣯⣻⣽
⡟⢎⣹⣵⣾⡿⣿⢷⣿⣿⣿⡿⣽⣻⣿⣟⡾⣝⣿⣿⣶⣿⡿⣭⣿⣳⢋⣾⣟⣷⡻⣜⣷⠟⠋⢀⣠⣴⣾⣏⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠖⠋⠁⣀⣤⣶⡿⣿⠽⡾⣿⣿⡙⣞⡿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠻⣿⣿⣿⣿⣿⣿⡗⣼⣿⣿⣷⡽⢾⣿⣿⣿⣿⡧⢚⠳⢰⣽⣿⡽⣯⡷⣿⡽⣯⣿⣾⣿⣿⣻⢾⣽⣳⣟⣾
⣭⣿⣿⢿⣽⣿⣦⣶⣽⢻⣯⣿⠷⠛⣩⣿⣯⠽⣿⣿⣟⡾⣽⢯⡟⡭⢿⣿⣻⣶⠿⢋⡴⣠⣶⡿⣿⣿⢿⣙⡻⣷⣦⠀⠀⠀⠀⠀⠀⣀⣤⡶⠛⣁⣴⢞⣫⣽⢟⡽⢫⣑⢛⣒⢳⣾⡯⣽⣾⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⢌⠿⣿⣿⣿⣿⡟⣼⣿⣿⣿⣽⣻⣿⣿⣿⣿⣇⣣⣷⣿⣿⣟⡿⣽⣻⣷⣿⣿⣿⣿⣿⣳⣯⣟⣾⣳⣿⣿
⣿⣿⣯⣹⣿⢾⣿⣿⡿⠟⢋⣡⣾⣿⣿⣻⢿⣷⡝⣿⣿⣟⣭⣛⡯⠵⣿⣿⡽⣹⣾⣿⣿⡿⣿⡽⣿⣟⡷⣯⣟⣿⠉⠀⠀⠀⠀⣠⣾⡿⣋⣴⣾⡹⣦⡿⣫⢓⡞⢊⣕⣺⣹⡎⣿⣟⣿⣿⣾⣿⣿⣇⠀⠀⠀⠀⠀⠀⠀⡈⢆⠲⡜⢯⣿⣿⣿⡳⢼⣿⣿⣿⡾⣽⣿⣿⣿⣿⣿⣿⣿⡿⣽⣾⣿⣿⣿⣿⣿⣿⡿⣟⣾⡽⣾⣽⣾⡿⣟⣾
⣿⣿⣿⣿⣽⠿⠛⣩⣴⣾⣿⣿⡿⣷⣻⣽⣯⢿⣿⣌⢿⣿⣿⣟⣯⢻⣿⡿⣽⣿⡷⣿⣶⡿⣽⣻⣿⣿⣿⣿⣾⣿⣷⡀⠀⣠⣾⣿⡿⣼⢿⣛⣴⣿⡫⣵⣛⢏⡶⣏⣺⣭⢷⣻⢷⡞⣿⣷⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠐⡂⢌⠲⣉⠖⡰⣿⣿⣱⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣟⡷⣿⢯⣷⣿⣿⣻⣽⣟⡿⣿
⡉⠉⠈⠉⠁⠘⠛⠛⠿⠿⣿⣷⣿⣽⣻⢾⣽⣻⢾⣿⣆⡻⣿⣿⡖⣿⣿⣽⣿⣟⣿⣷⣿⣟⣿⣽⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣯⢿⣾⡿⣧⣿⣭⢯⣟⣷⣩⣽⣳⣟⡿⣿⣻⣿⣾⣿⣿⣿⣿⣇⠀⠀⠀⠀⠈⠤⠑⠬⡱⣈⠎⡕⣿⣿⡎⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣷⣻⢾⣽⣿⣿⢿⣽⣞⣿⣳⣿⡽⢫
⣿⢿⣶⣶⣤⣬⣤⣉⣐⠡⠒⠜⢪⠝⡹⠻⠾⠿⣧⣿⣿⣷⣹⣿⡿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣷⣿⣿⣾⣽⣿⣷⣿⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⢀⠄⠑⡨⢡⠓⣄⠣⠜⡁⣿⣿⡇⢺⣽⣿⣿⣿⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣾⣿⣹⡟⢎⣵⣻
⣿⣿⣿⣾⡽⣷⣯⣿⣿⣿⣟⣾⡶⢦⣥⣭⣈⣃⠐⠢⠡⢨⠉⠻⣇⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠠⠈⣀⠃⢆⠱⡀⢓⠨⡁⣿⣿⣧⠒⣼⣿⣿⣿⣿⡾⣽⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣾⣿
⢶⣿⣾⣽⣿⣿⣳⣿⣾⣽⣻⣟⢿⢿⢶⡾⣿⣽⣿⣛⣷⠶⡾⣦⣽⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡆⠠⢁⠂⡍⠠⠂⠌⠄⢢⡅⡿⣿⣿⡎⢶⣻⣿⣿⣿⣿⣧⣛⡞⡙⢿⣿⣿⢿⣨⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣿⣿⣟⣿⣿⢯⣿⡟⣽⣿⡿⣿⣿⣿⣮⢷⣽⣶⣧⢿⡬⣛⣵⢒⢦⢲⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠐⢡⠂⠌⡠⠡⠈⣀⣶⣧⠀⢿⣿⣧⢓⣾⣿⣿⣿⣿⣿⣿⣾⣅⠀⠈⠙⢿⣯⣷⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠛⠻⠿⢿⣻⣟⡿⣙⣾⡿⣽⣳⢟⣼⣿⡓⣾⢟⣻⡷⠾⣷⣎⡝⢦⠣⡼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠁⡈⢂⠈⠐⢀⢰⣶⣿⣿⣿⡄⢸⣿⣿⣮⢾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀⠀⠈⠛⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣴⣤⣆⣤⣥⢿⣳⣻⡿⣝⡯⢷⡟⣞⣿⢱⣿⢎⡼⢃⡟⠴⡯⢱⠎⡕⡒⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⣴⣶⣿⣶⣧⣶⣿⣿⣿⣿⣿⡇⠀⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠈⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⣏⣾⡿⣟⡯⠫⠏⠉⠙⠛⠿⠷⢿⣼⡃⣿⢏⣏⢏⡳⣜⣣⣝⣦⡷⣌⠱⣸⣧⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣇⣼⡿⣿⣿⣿⣻⡼⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣄⠀⠀⠈⠙⠿⣿⣿⣿⣿⣿⣟⣿⣿
⣿⣻⡽⣯⢧⡟⣿⡶⠖⠲⣤⣤⡾⢧⣓⡯⢺⣌⡛⢶⣉⣡⣉⠉⠓⠌⣡⡟⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⡿⣯⣽⡿⣿⣿⣷⣿⣵⢫⡞⡽⣻⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣄⡀⠀⠈⠛⢿⡿⣿⣿⣿⣿
⢿⣳⢿⣼⠣⣛⠶⣭⣛⢿⡻⣍⢏⠧⡼⡸⢅⡎⡙⠦⢭⠩⢍⣟⢛⣲⡟⠀⣿⣿⣿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⣽⣾⢻⡜⡽⣿⣿⣿⣿⣿⣾⣵⣣⢏⣴⣨⢍⠩⣉⣉⣉⢉⠉⠉⡉⠓⢲⡀⠀⠀⠙⢷⣮⣍⡛
*/
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include "richest.h"
using namespace std;
#define sz(x) (int) (x).size()
#define i64 int64_t
#define all(x) (x).begin(), (x).end()
vector<int> a,b,c;
int subtask_1(int N) {
a.resize(0);
b.resize(0);
for (int i=0; i<N; i++) {
for (int j=i+1; j<N; j++) {
a.push_back(i);
b.push_back(j);
}
}
assert(sz(a)<=499500);
c = ask(a,b);
set<int> ok;
for (int i=0; i<N; i++) {
ok.insert(i);
}
for (int i=0; i<sz(c); i++) {
if (a[i]==c[i]) {
if (ok.count(b[i])) ok.erase(b[i]);
} else {
if (ok.count(a[i])) ok.erase(a[i]);
}
}
assert(sz(ok)==1);
return *(ok.begin());
}
const int mxn=1e6+5;
vector<int> ops = {2,2,2,2,3,6,18,1000000};
int good[mxn];
vector<int> cv,pv;
int subtask_2(int N) {
memset(good,0x3f,sizeof(good));
cv.clear(); pv.clear();
for (int i=0; i<N; i++) {
cv.push_back(i);
}
for (int DIV : ops) {
vector<int> cbk;
a.clear();
b.clear();
for (int i=0; i<sz(cv); i+=DIV) {
cbk.clear();
for (int j=i; j<min(sz(cv),i+DIV); j++) {
cbk.push_back(cv[j]);
}
for (int i1=0; i1<sz(cbk); i1++) {
for (int i2=i1+1; i2<sz(cbk); i2++) {
a.push_back(cbk[i1]);
b.push_back(cbk[i2]);
}
}
}
c = ask(a,b);
for (int i=0; i<sz(c); i++) {
if (a[i] == c[i]) {
good[b[i]]=0;
} else {
good[a[i]]=0;
}
}
swap(cv,pv);
cv.clear();
for (int i : pv) {
if (good[i]) cv.push_back(i);
}
if (sz(cv)==1) {
return cv[0];
}
}
}
int richest(int N, int T=1, int S=1) {
if (T==1) return subtask_1(N);
assert(N==1000000);
return subtask_2(N);
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Pretest #1:
score: 15
Accepted
time: 632ms
memory: 24540kb
input:
1000 1 499500 957319859
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Pretest #2:
score: 56
Acceptable Answer
time: 2046ms
memory: 99616kb
input:
1000000 20 2000000 29091473
output:
Partially correct Case 2, 56 / 85, maxt = 8, maxs = 1100120 18364862737241168673 0.658824 10645090175016484801
result:
points 0.658824 Partially correct Case 2, 56 / 85, maxt = 8, maxs = 1100120
Final Tests
Test #1:
score: 15
Accepted
time: 629ms
memory: 26168kb
input:
1000 1 499500 957319857
output:
Correct 7127326332295218295 1.000000 1331569654267968081
result:
points 1.0 Correct
Test #2:
score: 56
Acceptable Answer
time: 2060ms
memory: 99612kb
input:
1000000 20 2000000 29091471
output:
Partially correct Case 2, 56 / 85, maxt = 8, maxs = 1100120 18364862737241168673 0.658824 10645090175016484801
result:
points 0.658824 Partially correct Case 2, 56 / 85, maxt = 8, maxs = 1100120