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
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

const int MAXN = 3e5 + 3;

int rk[MAXN], pt[MAXN], last[MAXN];
long long sum[MAXN], pre[MAXN], ans[MAXN];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(9);

  int n, w;
  cin >> n >> w;
  rk[0] = 1;
  for (int i = 0; i < w; ++i) {
    int k, x, p;
    for (cin >> k; k; --k) {
      cin >> x;
      p = pt[x];
      sum[p] += 1ll * rk[p] * (i - last[p]);
      last[p] = i, ++rk[p];
      ans[x] += sum[p] - pre[x];

      p = ++pt[x];
      sum[p] += 1ll * rk[p] * (i - last[p]);
      last[p] = i;
      if (rk[p] == 0) rk[p] = 1;
      pre[x] = sum[p];
    }
  }

  for (int i = 1; i <= n; ++i) {
    int p = pt[i];
    sum[p] += 1ll * rk[p] * (w - last[p]);
    last[p] = w;
    cout << (ans[i] + sum[p] - pre[i]) * 1.0 / w << "\n";
  }

  return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

# include <bits/stdc++.h>
# define R register
# define N 10010
# define LL long long
# define db double
using namespace std;

int n,m,l[N],r[N],a[N],ans[N],cnt,p[N];

int main(){
  scanf("%d",&n);
  for (int i=1; i<=n; ++i) scanf("%d%d",&l[i],&r[i]);
  l[1]--,r[n]++;
  scanf("%d",&m);
  for (int i=1; i<=m; ++i) scanf("%d",&a[i]);
  for (int i=1,t=1; i<=n; ++i)
  {
    int sum = 0;
    while (t<=m && a[t]<l[i]) t++;
    while (t<=m && a[t]<r[i])
    {
      sum++;
      t++;
    }
    if (t <= m && a[t] == r[i]) sum++;
    if (sum > 2) printf("impossible"),exit(0);
    else p[i] = sum;
  }

  for (int i=1,t=1; i<=n; ++i)
  {
    if (p[i] == 2) continue;
    while (t+1<=m && a[t+1]<=r[i]) t++;
    if (i < n && a[t] != r[i] && p[i+1] != 2 && r[i]==l[i+1]) p[i+1]++,p[i]++,ans[++cnt] = r[i];
  }
  for (int i=1; i<=cnt; ++i) a[++m] = ans[i];
  sort(a+1,a+m+1);
  for (int i=1,t=1; i<=n; ++i)
  {
    if (p[i] == 2) continue;
    while (t<=m && a[t]<l[i]) t++;
    if (t > m)
    {
      for (int j=l[i]+1; j<r[i]; ++j)
      {
        ans[++cnt] = j;
        p[i]++;
        if (p[i] == 2) break;
      }
      continue;
    }
//		printf("%d - %d\n",i,t);
    for (int j=l[i]+1; j<a[t]; ++j)
    {
      ans[++cnt] = j;
      p[i]++;
      if (p[i] == 2) break;
    }
    if (p[i] == 2) continue;
    while (t+1<=m && a[t+1]<=r[i] && p[i]<2)
    {
      for (int j=a[t]+1; j<a[t+1]; ++j)
      {
        ans[++cnt] = j;
        p[i]++;
        if (p[i] == 2) break;
      }
      t++;
    }
    if (p[i] == 2) continue;
    for (int j=a[t]+1; j<r[i]; ++j)
    {
      ans[++cnt] = j;
      p[i]++;
      if (p[i] == 2) break;
    }
  }
  sort(ans+1,ans+cnt+1);
  printf("%d\n",cnt);
  for (int i=1; i<=cnt; ++i) printf("%d ",ans[i]);
  return 0;
}
/*
4
0 18
18 28
28 40
49 60
3
6 12 35

*/

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

const int MAXN = 2e5 + 3;

int f[MAXN];
map<int, vector<int>> bin;
tuple<int, int, int> ans[MAXN];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int n;
  cin >> n;
  for (int i = 1, m, d; i <= n; ++i) {
    f[i] = i;
    cin >> m;
    for (int j = 0; j < m; ++j) {
      cin >> d;
      bin[d].emplace_back(i);
    }
  }

  int cnt = 1;
  for (auto &p : bin) {
    int r = p.first;
    auto &vs = p.second;
    int sz = vs.size();
    if (sz <= 1) continue;
    int u = vs[0];
    for (int i = 1; i < sz; ++i) {
      int v = vs[i];
      if (find(u) == find(v)) continue;
      f[f[v]] = f[u];
      ans[cnt++] = {u, v, r};
      if (cnt == n) break;
    }
    if (cnt == n) break;
  }

  if (cnt < n) {
    cout << "impossible\n";
  } else {
    for (int i = 1, p, q, r; i < n; ++i) {
      tie(p, q, r) = ans[i];
      cout << p << " " << q << " " << r << "\n";
    }
  }

  return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=507;
double a[MAXN];

int main(){
    //freopen("in.txt","r",stdin);
    int n,k,up,down;
    double coe,res;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;++i)
        scanf("%lf",&a[i]);
    int i=0;
        res=0.0;
        coe=1.0*k/n;
        res=coe*a[i];
        up=n-k;down=n-1;
        for(int j=i-1,jinf=i-n+k;j>=jinf;--j){
            coe*=1.0*up/down;
            --up;--down;
            res+=coe*a[(j+n)%n];
        }
        printf("%.7lf",res);
    ++i;
    for(;i<n;++i){
        res=0.0;
        coe=1.0*k/n;
        res=coe*a[i];
        up=n-k;down=n-1;
        for(int j=i-1,jinf=i-n+k;j>=jinf;--j){
            coe*=1.0*up/down;
            --up;--down;
            res+=coe*a[(j+n)%n];
        }
        printf(" %.7lf",res);
    }
    putchar('\n');
    return 0;
}

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

const int MAXN = 1e5 + 3;

int h[MAXN];
pair<long long, int> f[MAXN], p[MAXN];

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  cout << fixed << setprecision(10);

  int n, k;
  cin >> n >> k;
  int max_d = 0;
  for (int i = 0; i <= n; ++i) cin >> h[i];
  for (int i = 1; i <= n; ++i) max_d = max(max_d, h[i] - h[i - 1]);

  for (double x; k; --k) {
    cin >> x;
    int g = x * 10 + 0.5;
    if (g > max_d) {
      cout << "-1\n";
      continue;
    }
    for (int i = 0; i <= n; ++i) p[i] = f[i] = make_pair(h[i] - 1ll * g * i, i);
    sort(f, f + n + 1);

    int i = n + 1;
    double ans = 0;
    for (int _ = 0; _ <= n; ++_) {
      int j = f[_].second;
      if (j > i) {
        double ext = 0;
        if (j < n && p[j + 1].first != p[j].first)
          ext = max(ext, fabs(1.0 * (p[j].first - p[i].first) /
                              (p[j + 1].first - p[j].first)));
        if (i > 0 && p[i - 1].first != p[i].first)
          ext = max(ext, fabs(1.0 * (p[j].first - p[i].first) /
                              (p[i].first - p[i - 1].first)));
        if (ext > 1) ext = 1;
        ans = max(ans, j - i + ext);
      }
      i = min(i, j);
    }

    cout << ans << "\n";
  }

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

# include <bits/stdc++.h>
# define R register
# define N 1000010
# define LL long long

using namespace std;

int n,a[N],b[N];

int main(){
  scanf("%d",&n);
  for (int i=1; i<=n; ++i) scanf("%d",&a[i]),b[i] = a[i];
  sort(a+1,a+n+1);
  int s = 1,t = n;
  while (s < n && a[s] == b[s]) s++;
  while (t > s && a[t] == b[t]) t--;
  for (int i=s,j=t; i<=t; ++i,--j)
    if (a[i] != b[j]) printf("impossible\n"),exit(0);
  printf("%d %d\n",s,t);
}