fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 (  )
  3.  *    created: 23.12.2022 10:08:02
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define nn "\n"
  11.  
  12. const int N = 1e6 + 5;
  13. int sz[N], par[N];
  14. int n, k;
  15.  
  16. void make_set(int a){
  17.     par[a] = a;
  18.     sz[a] = 1;
  19. }
  20.  
  21. int get(int v){
  22.     if(v == par[v]) return v;
  23.     return par[v] = get(par[v]);
  24. }
  25.  
  26. void union_sets(int a, int b){
  27.     a = get(a);
  28.     b = get(b);
  29.     if(a != b){
  30.         par[b] = a;
  31.         sz[a] += sz[b];
  32.     }
  33. }
  34.  
  35. void solve(){
  36.     if (!(cin >> n >> k)) return;
  37.  
  38.     // Có N + 1 nếp gấp đánh số từ 0 đến N
  39.     for(int i = 0; i <= n; i++) {
  40.         make_set(i);
  41.     }
  42.  
  43.     int l = 0, r = n;
  44.  
  45.     for(int i = 1; i <= k; i++){
  46.         int x; 
  47.         cin >> x;
  48.         x = get(x); // Lấy đại diện hiện tại của vị trí x
  49.  
  50.         int left_len = x - l;
  51.         int right_len = r - x;
  52.  
  53.         // Phần ngắn hơn sẽ được gấp chồng lên phần còn lại
  54.         // Nếu hai phần bằng nhau (left_len == right_len), gấp bên trái lên bên phải
  55.         if(left_len <= right_len){
  56.             // Gấp phần bên trái [l, x] sang bên phải qua trục x
  57.             for(int i = l; i <= x; i++){
  58.                 int u = get(i);
  59.                 int v = get(2 * x - i); // Điểm đối xứng qua x
  60.                 if (u != v) {
  61.                     union_sets(v, u); // Gộp vào phía bên phải
  62.                 }
  63.             }
  64.             l = x + 1; // Biên trái dịch chuyển sau khi phần bên trái đã bị gấp chồng lên
  65.         } else {
  66.             // Gấp phần bên phải [x, r] sang bên trái qua trục x
  67.             for(int i = x; i <= r; i++){
  68.                 int u = get(i);
  69.                 int v = get(2 * x - i); // Điểm đối xứng qua x
  70.                 if (u != v) {
  71.                     union_sets(v, u); // Gộp vào phía bên trái
  72.                 }
  73.             }
  74.             r = x - 1; // Biên phải dịch chuyển sau khi phần bên phải đã bị gấp chồng lên
  75.         }
  76.     }
  77.  
  78.     // In kết quả ra file BANDO.OUT
  79.     cout << r - l + 1 << nn;
  80.     for(int i = l; i <= r; i++){
  81.         cout << sz[get(i)] << " ";
  82.     }
  83.     cout << nn;
  84. }
  85.  
  86. signed main() {
  87.  
  88.     ios_base::sync_with_stdio(0);
  89.     cin.tie(0);
  90.     cout.tie(0);
  91.  
  92.     solve();
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0.01s 5704KB
comments (?)
stdin
copy 
7 2
3 2
stdout
copy 
3
2 2 1
https://ideone.com/92bGGs
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!