极限压缩 - 题目

传统 1000 ms 256 MiB

标准 IO

文本比较 admin 标签

经常有人抱怨到：”这个**短码竞赛，说是要短码，其实考的是***算法！挂羊头卖狗肉！“

而抱怨的人混入命题组后，决心出一道题以证明这个比赛不需要考算法，完全可以只考短码。为此他出了这样一道题：

给定如下 C++ 代码，请修改此程序，在输入满足输入格式的描述时，输出能够保持不变的前提条件下，尽可能缩短程序并在下方提交。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct pos {
    int x;
	int v;
    int l;
	int r;
	int id;
    void read(int i) {
        scanf("%d%d", &x, &v);
        l = i - 1;
        r = i + 1;
        id = i;
    }
} pos[int(1e5) + 10];
struct coll {
    int i, j;
    bool operator <(const coll& other) const {
        return 1ll * (pos[j].x - pos[i].x) * (pos[other.i].v - pos[other.j].v) > 1ll * (pos[other.j].x - pos[other.i].x) * (pos[i].v - pos[j].v);
    }
    bool operator >(const coll& other) const {
        return 1ll * (pos[j].x - pos[i].x) * (pos[other.i].v - pos[other.j].v) < 1ll * (pos[other.j].x - pos[other.i].x) * (pos[i].v - pos[j].v);
    }
    bool isOK() const {
        return pos[i].v == pos[j].v;
    }
    bool isBAD() const {
    	return pos[i].v != pos[j].v;
	}
};
bool vt[int(1e5) + 10];
int main() {
    int n;
    scanf("%d", &n);
    priority_queue<coll> p;
    memset(vt,0,sizeof(vt));
    for (int i = 1; i <= n; i++) {
        pos[i].id = i;
    }
    for (int i = 1; i <= n; i++) {
        pos[i].read(i);
    }
    for (int i = 1; i < n; i++) {
        p.emplace(coll{i, i + 1});
    }
    pos[0].l = 0; pos[0].r = 1; pos[0].id = 0;
    pos[n + 1].l = n; pos[n + 1].r = n + 1; pos[n + 1].id = n + 1;
    while (!p.empty()) {
        if (p.top().isOK()) break;
        int xi = p.top().i;
		int xj = p.top().j;
        p.pop();
        if (vt[xi] || vt[xj]) continue;
        vt[xi] = 1;
		vt[xj] = 1;
        pos[pos[xi].l].r = pos[xj].r;
        pos[pos[xj].r].l = pos[xi].l;
        if (pos[xi].l > 0 && pos[xj].r <= n){
        	p.emplace(coll{pos[xi].l, pos[xj].r});
		}
    }
    int cnt = 0,fac = 1;
    for (int i = 1; i <= n; i++) {
    	if(vt[i] == 0){
    		cnt++;
    		fac = fac*i % mod;
		}
    }
    printf("%d\n", cnt);
    bool fir = true;
    for (int i = 1; i <= n; i++) {
        if (!vt[i]) {
            if (fir){
            	fir = false;
			}
			else{
				putchar(' ');
			}
            printf("%d", i);
        }
    }
    puts("");
}

第一行一个正整数 $n（1 \leq n \leq 10^5)$ 。

下面 $n$ 行，每行两个正整数 $a_i,b_i(-10^9 \leq a_i,b_i \leq 10^9)$ 。

输入数据保证对于任意 $1 \leq i \leq n-1$ 都有 $a_{i-1} \leq a_i$ 。

输出请参考题目描述中的程序。

样例输入

样例输出

2
1 6

#355. 极限压缩

题目描述

输入格式

输出格式

样例

样例输入

样例输出