MnZn求助,Time limit exceeded on test 11
查看原帖
MnZn求助,Time limit exceeded on test 11
510555
ImposterAnYu楼主2022/10/19 22:31
#include<bits/stdc++.h>
#define int1 long long
#define N 200005
using namespace std;
int1 n,m,k,i,ans[N],cnt;
bool b[N];
struct owo{
	int1 x,id;
	bool operator < (const owo &b) const{
		return x < b.x;
	}
} a[N];
int1 read(){
    int1 x = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(int1 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        print(x / 10);
    }
    putchar(x % 10 + 48);
    return ;
}
int1 find_i(int1 l){
	int1 i;
	for(i = l; i <= n && b[i]; i++);
	return i;
}
int main(){
	n = read(),m = read(),k = read();
	for(i = 1; i <= n; i++){
		a[i].x = read(),a[i].id = i;
	}
	sort(a + 1,a + n + 1);
	for(i = find_i(1); i <= n; i = find_i(1)){
		cnt++;
		for(; i <= n; i = find_i(upper_bound(a + i + 1,a + n + 1,(owo){a[i].x + k,0}) - a)){
			ans[a[i].id] = cnt,b[i] = 1;
		}
	}
	print(cnt);
	putchar('\n');
	for(i = 1; i <= n; i++){
		print(ans[i]);
		putchar(' ');
	}
	return 0;
} 
2022/10/19 22:31
加载中...