【CF1237C】Balanced Removals(降维)
2024-10-07 08:46:58
题意:三维平面上有n个点,每个点的坐标为(x[i],y[i],z[i]),n为偶数
现在要求取n/2次,每次取走一对点(x,y),要求没有未被取走的点在以x和y为对角点的矩形中
要求给出任意一组合法方案
n<=5e4,abs(x[i],y[i],z[i])<=1e8
思路:我觉得托老爷的官方题解的google机翻已经够简明了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 200010
#define M 200010
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
ll INF=1e15;
int dx[]={-,,,};
int dy[]={,,-,}; struct node
{
int x,y,z,id;
}a[N],b[N]; bool cmp(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.z<b.z;
} int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} int main()
{
int n=read();
rep(i,,n)
{
a[i].x=read(),a[i].y=read(),a[i].z=read();
a[i].id=i;
}
sort(a+,a+n+,cmp);
int i,j,k,m=;
for(i=;i<=n;)
{
j=i;
while(j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y) j++;
for(k=i;k+<=j;k+=) printf("%d %d\n",a[k].id,a[k+].id);
if(k==j-) b[++m]=a[k];
i=j;
}
n=;
for(i=;i<=m;)
{
j=i;
while(j<=m&&b[i].x==b[j].x) j++;
for(k=i;k+<=j;k+=) printf("%d %d\n",b[k].id,b[k+].id);
if(k==j-) a[++n]=b[k];
i=j;
}
for(i=;i<=n;i+=) printf("%d %d\n",a[i].id,a[i+].id);
return ;
}
最新文章
- 为什么现在更多需要用的是 GPU 而不是 CPU,比如挖矿甚至破解密码?
- POJ1154
- 利用Arraylist输入学生的成绩,求出平均分和总分。
- Mysql主从库同步错误:1062 Error &#39;Duplicate entry &#39;1438019&#39;
- nodejs框架express4.x 学习--安装篇
- poj2823:单调队列入门题
- 了解HTML5和“她”的 API (一)
- Swift和Javascript的神奇魔法
- (转)IntelliJ IDEA 破解方法
- error: stray &#39;\357&#39; in program编程出错的总结
- Cocos2D:塔防游戏制作之旅(四)
- go语言时间比较
- [物理学与PDEs]第3章第3节 电导率 $\sigma$ 为无穷时的磁流体力学方程组 3.3 磁场线``冻结&#39;&#39;原理
- Python3学习之路~7.4 动态导入模块
- jmeter5.0生成html报告 快速入门
- windows环境下Oracle数据库冷备份和恢复
- Node 在 Centos7 系统下的安装
- vue+iview实现一行平均五列布局
- github 最新项目快报
- topK 算法