首页 > 代码库 > CodeForces 733D Kostya the Sculptor

CodeForces 733D Kostya the Sculptor

排序。把每一个长方体拆成$6$个做,然后排序做即可。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - 0;        c = getchar();    }}struct X{    int a,b,c,id;}s[600010],t[600000];int n,sz;void add(int A,int B,int C,int ID){    s[sz].a=A;    s[sz].b=B;    s[sz].c=C;    s[sz].id=ID;    sz++;}bool F(int x,int y){    if(s[x].a!=s[y].a) return 0;    if(s[x].b!=s[y].b) return 0;    if(s[x].c!=s[y].c) return 0;    if(s[x].id!=s[y].id) return 0;    return 1;}bool cmp(X a,X b){    if(a.a!=b.a) return a.a<b.a;    if(a.b!=b.b) return a.b<b.b;    if(a.c!=b.c) return a.c<b.c;    return a.id<b.id;}int main(){    cin>>n;    for(int i=1;i<=n;i++)    {        int a,b,c; cin>>a>>b>>c;        add(a,b,c,i); add(b,a,c,i);        add(a,c,b,i); add(c,a,b,i);        add(b,c,a,i); add(c,b,a,i);    }    sort(s,s+sz,cmp);    sz=0; t[sz++]=s[0];    for(int i=1;i<6*n;i++)    {        if(F(i,i-1)==1) continue;        t[sz++]=s[i];    }/*    for(int i=0;i<sz;i++)    {        printf("%d %d %d %d\n",t[i].a,t[i].b,t[i].c,t[i].id);    }    */    int mx=0,ans1,ans2,ans3;    for(int i=0;i<sz;i++)    {        if(min(t[i].a,min(t[i].b,t[i].c))>mx)        {            mx=min(t[i].a,min(t[i].b,t[i].c));            ans1=1; ans2=t[i].id;        }        if(i>=1&&t[i].a==t[i-1].a&&t[i].b==t[i-1].b)        {            if(min(t[i].a,min(t[i].b,t[i].c+t[i-1].c))>mx)            {                mx=min(t[i].a,min(t[i].b,t[i].c+t[i-1].c));                ans1=2; ans2=t[i].id; ans3=t[i-1].id;            }        }    }    if(ans1==1) printf("1\n%d\n",ans2);    else printf("2\n%d %d\n",ans2,ans3);    return 0;}

 

CodeForces 733D Kostya the Sculptor