Submission #520093

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
520093	2022-01-28 10:32:40	amunduzbaev	Space Pirate (JOI14_space_pirate)	C++14	80 / 100	1486 ms	148292 KiB

space_pirate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
void solve(int n, int k, vector<int>& p){
  vector<vector<int>> pp(n);
  vector<vector<int>> d(n, vector<int>(n, 2e18));
  for(int i=0;i<n;i++){
    d[i][i] = 0, pp[i].push_back(i);
    while(d[i][p[pp[i].back()]] == 2e18){
      d[i][p[pp[i].back()]] = d[i][pp[i].back()] + 1;
      pp[i].push_back(p[pp[i].back()]);
    }
  }
  
  auto last = [&](int x) { return pp[x].back(); };
  auto loop = [&](int x) { return p[last(x)]; };
  
  vector<int> sz(n);
  for(int i=0;i<n;i++){
    sz[i] = d[i][last(i)] - d[i][loop(i)] + 1;
  }
  
  auto find = [&](int a, int b){
    if(b < (int)pp[a].size()){
      return pp[a][b];
    }
    int cnt = (b - (int)pp[a].size()) % sz[a];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 37 / 37
• Subtask 3: 33 / 33
• Subtask 4: 0 / 20