fork download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 100100
  18. #define PRIME 31
  19. #define INC 100000
  20. #define MOD 1000000007
  21. #define PI 3.1415926535897932384
  22. #define F first
  23. #define S second
  24. #define pb push_back
  25. #define mp make_pair
  26. typedef long long ll;
  27.  
  28. struct node{
  29.     int s, e, val;
  30. };
  31.  
  32. int n, vet[MAX], res[MAX];
  33. node seg_tree[4*MAX];
  34.  
  35. void build(int s, int e, int pos){
  36.     seg_tree[pos].s = s; seg_tree[pos].e = e;
  37.     seg_tree[pos].val = e-s+1;
  38.  
  39.     if(e > s){
  40.         int mid = s+(e-s)/2;
  41.         build(s, mid, 2*pos);
  42.         build(mid+1, e, 2*pos+1);
  43.     }
  44. }
  45.  
  46. int query(int val, int pos){
  47.  
  48.     if(seg_tree[pos].s == seg_tree[pos].e) return seg_tree[pos].s;
  49.  
  50.     if(val <= seg_tree[2*pos+1].val) return query(val, 2*pos+1);
  51.     return query(val-seg_tree[2*pos+1].val, 2*pos);
  52. }
  53.  
  54. void update(int ind, int pos){
  55.     int mid = seg_tree[pos].s+(seg_tree[pos].e-seg_tree[pos].s)/2;
  56.  
  57.     seg_tree[pos].val--;
  58.     if(seg_tree[pos].e == seg_tree[pos].s) return;
  59.  
  60.     if(ind <= mid) update(ind, 2*pos);
  61.     else update(ind, 2*pos+1);
  62. }
  63.  
  64. int main(){
  65.     //std::ios_base::sync_with_stdio(false);
  66.     //freopen("in.txt", "r", stdin);
  67.     //freopen("out.txt", "w", stdout);
  68.  
  69.     int t;
  70.     cin >> t;
  71.     for(int test = 1;test <= t;test++){
  72.  
  73.         cin >> n;
  74.  
  75.         build(0, n-1, 1);
  76.  
  77.         for(int i = 0;i < n;i++) scanf("%d", &vet[i]);
  78.  
  79.         int posi;
  80.         for(int i = n-1;i >= 0;i--){
  81.             posi = query(vet[i]+1, 1);
  82.  
  83.             if(!i){ cout << "Case " << test << ": " << posi+1 << endl; break; }
  84.  
  85.             update(posi, 1);
  86.         }
  87.     }
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0s 8936KB
comments (?)
stdin
copy 
3
3
0 0 0
3
0 1 2
3
0 1 0
stdout
copy 
Case 1: 1
Case 2: 3
Case 3: 2
https://ideone.com/DztBlt
language:
C++14 (gcc 8.3)
created:
8 years 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!