Codeforces Round #187 (Div. 2) C. Sereja and Contest

Oct 20, 2013#implement #CodeForce57

AI Translation

This post is translated from Chinese into English through AI.View Original

AI-generated summary

The Codeforces Round #187 (Div. 2) problem "Sereja and Contest" involves calculating ranks using a formula and removing contestants if their calculated rank is below a certain threshold. The formula involves subtracting a value from previous numbers based on the contestant's position. The algorithm ensures that contestants who have not been removed before will not be removed in future rounds. The solution involves iterating through the contestants and removing those who do not meet the rank criteria.

The problem description is about a code server that has a formula for calculating rank.

If the calculated di is less than k, then the person should be deleted and recalculated.

Then, continue to find the numbers of all deleted people.

It can be observed that the formula is obtained by subtracting ai multiplied by (n-i) from the numbers before ai.

So if no one before the current point i is deleted, it can be guaranteed that the rank will not change in the future rounds.

If the person to be deleted is encountered, delete that point, increase the deletion count by 1, and the formula should have an additional i-del to represent the actual position.

//  
//        GGGGGGGGGGGGG        CCCCCCCCCCCCC               AAA  
//     GGG::::::::::::G     CCC::::::::::::C              A:::A  
//   GG:::::::::::::::G   CC:::::::::::::::C             A:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C            A:::::::A  
// G:::::G       GGGGGG C:::::C       CCCCCC           A:::::::::A  
//G:::::G              C:::::C                        A:::::A:::::A  
//G:::::G              C:::::C                       A:::::A A:::::A  
//G:::::G    GGGGGGGGGGC:::::C                      A:::::A   A:::::A  
//G:::::G    G::::::::GC:::::C                     A:::::A     A:::::A  
//G:::::G    GGGGG::::GC:::::C                    A:::::AAAAAAAAA:::::A  
//G:::::G        G::::GC:::::C                   A:::::::::::::::::::::A  
// G:::::G       G::::G C:::::C       CCCCCC    A:::::AAAAAAAAAAAAA:::::A  
//  G:::::GGGGGGGG::::G  C:::::CCCCCCCC::::C   A:::::A             A:::::A  
//   GG:::::::::::::::G   CC:::::::::::::::C  A:::::A               A:::::A  
//     GGG::::::GGG:::G     CCC::::::::::::C A:::::A                 A:::::A  
//        GGGGGG   GGGG        CCCCCCCCCCCCCAAAAAAA                   AAAAAAA  
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
#include <climits>  
#include <vector>  
#include <set>  
#include <map>  
#include <queue>  
#include <cctype>  
#include <utility>  
#include <ctime>  
using namespace std;  
#ifdef DEBUG  
#define VAR(a,b) decltype(b) a=(b)  
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)  
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);  
#else  
#define VAR(a,b) \_\_typeof(b) a=(b)  
#define debug(...)  
#define gettime()  
#endif  
typedef unsigned int uint;  
typedef long long int Int;  
typedef unsigned long long int UInt;  
#define Set(a,s) memset(a,s,sizeof(a))  
#define Write(w) freopen(w,"w",stdout)  
#define Read(r) freopen(r,"r",stdin)  
#define Pln() printf("\\n")  
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()  
#define De(x)printf(#x"%d\\n",x)  
#define For(i,x)for(int i=0;i<x;i++)  
#define CON(x,y) x##y  
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\  
    printf("%d ",dp\[htx\]\[hty\]);}Pln();}  
#define M 30005  
#define PII pair<int,int\>  
#define PB push\_back  
#define oo INT\_MAX  
#define Set\_oo 0x3f  
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)  
#define eps 1e-6  
#define X first  
#define Y second  
clock\_t start\_time=clock(), end\_time;  
bool xdy(double x,double y){return x>y+eps;}  
bool xddy(double x,double y){return x>y-eps;}  
bool xcy(double x,double y){return x<y-eps;}  
bool xcdy(double x,double y){return x<y+eps;}  
int min3(int x,int y,int z){  
    int tmp=min(x,y);  
    return min(tmp,z);  
}  
int max3(int x,int y,int z){  
    int tmp=max(x,y);  
    return max(tmp,z);  
}  
int n;  
Int x\[200005\];  
Int k;  
int main() {  
    ios\_base::sync\_with\_stdio(0);  
    while(~scanf("%d %I64d",&n,&k)){  
        for(int i=1;i<=n;i++)scanf("%I64d",&x\[i\]);  
        Int all=0;  
        int delcnt=0;  
        for(int i=1;i<=n;i++){  
            Int t=all-(n-i)\*x\[i\]\*(i-1-delcnt);  
            if(t>=k)  
                all+=x\[i\]\*(i-1-delcnt);  
            else{  
                printf("%d\\n",i);  
                delcnt++;  
            }  
        }  
    }  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
}

// // GGGGGGGGGGGGG CCCCCCCCCCCCC AAA // GGG::::::::::::G CCC::::::::::::C A:::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::::A // G:::::G GGGGGG C:::::C CCCCCC A:::::::::A //G:::::G C:::::C A:::::A:::::A //G:::::G C:::::C A:::::A A:::::A //G:::::G GGGGGGGGGGC:::::C A:::::A A:::::A //G:::::G G::::::::GC:::::C A:::::A A:::::A //G:::::G GGGGG::::GC:::::C A:::::AAAAAAAAA:::::A //G:::::G G::::GC:::::C A:::::::::::::::::::::A // G:::::G G::::G C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A // G:::::GGGGGGGG::::G C:::::CCCCCCCC::::C A:::::A A:::::A // GG:::::::::::::::G CC:::::::::::::::C A:::::A A:::::A // GGG::::::GGG:::G CCC::::::::::::C A:::::A A:::::A // GGGGGG GGGG CCCCCCCCCCCCCAAAAAAA AAAAAAA #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <climits> #include <vector> #include <set> #include <map> #include <queue> #include <cctype> #include <utility> #include <ctime> using namespace std; #ifdef DEBUG #define VAR(a,b) decltype(b) a=(b) #define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_) #define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC); #else #define VAR(a,b) \_\_typeof(b) a=(b) #define debug(...) #define gettime() #endif typedef unsigned int uint; typedef long long int Int; typedef unsigned long long int UInt; #define Set(a,s) memset(a,s,sizeof(a)) #define Write(w) freopen(w,"w",stdout) #define Read(r) freopen(r,"r",stdin) #define Pln() printf("\\n") #define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln() #define De(x)printf(#x"%d\\n",x) #define For(i,x)for(int i=0;i<x;i++) #define CON(x,y) x##y #define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\ printf("%d ",dp\[htx\]\[hty\]);}Pln();} #define M 30005 #define PII pair<int,int\> #define PB push\_back #define oo INT\_MAX #define Set\_oo 0x3f #define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a) #define eps 1e-6 #define X first #define Y second clock\_t start\_time=clock(), end\_time; bool xdy(double x,double y){return x>y+eps;} bool xddy(double x,double y){return x>y-eps;} bool xcy(double x,double y){return x<y-eps;} bool xcdy(double x,double y){return x<y+eps;} int min3(int x,int y,int z){ int tmp=min(x,y); return min(tmp,z); } int max3(int x,int y,int z){ int tmp=max(x,y); return max(tmp,z); } int n; Int x\[200005\]; Int k; int main() { ios\_base::sync\_with\_stdio(0); while(~scanf("%d %I64d",&n,&k)){ for(int i=1;i<=n;i++)scanf("%I64d",&x\[i\]); Int all=0; int delcnt=0; for(int i=1;i<=n;i++){ Int t=all-(n-i)\*x\[i\]\*(i-1-delcnt); if(t>=k) all+=x\[i\]\*(i-1-delcnt); else{ printf("%d\\n",i); delcnt++; } } } }