首页 > 其他 > 详细

Codeforces 1254C/1255F Point Ordering (交互题)

时间:2019-12-06 14:31:41      阅读:96      评论:0      收藏:0      [点我收藏+]

题目链接

http://codeforces.com/contest/1254/problem/C

题解

sb题。
第一次,通过\((n-2)\)次询问2确定\(p[2]\),也就是从\(1\)来看“最逆时针”的点。
第二次,通过\((n-2)\)次询问1确定每个点与\(a_1a_{p_2}\)这条直线的距离,并将所有点按该值排序。设排序后的数组是\(s_3,s_4,...\).
第三次,通过\((n-3)\)次询问2将所有点定序。我们实际上就是要将\((n-2)\)个点分成两组,一组从前往后,一组从后往前。每次询问2 1 s[i] s[i+1], 若答案为\(1\), 说明\(s_i\)是在第一组,否则在第二组。
时间复杂度\(O(n\log n)\), 总询问次数\((3n-7)\).

代码

#include<bits/stdc++.h>
#define pli pair<llong,int>
#define llong long long
using namespace std;

const int N = 1000;
int p[N+3]; pli s[N+3];
int n;

int main()
{
    scanf("%d",&n);
    p[1] = 1; p[2] = 2;
    for(int i=3; i<=n; i++)
    {
        printf("2 %d %d %d\n",1,i,p[2]); fflush(stdout);
        int x; scanf("%d",&x); if(x==1) {p[2] = i;}
    }
    for(int i=2; i<=n; i++)
    {
        if(i==p[2]) continue;
        printf("1 %d %d %d\n",1,p[2],i); fflush(stdout);
        scanf("%I64d",&s[i].first); s[i].second = i;
    }
    sort(s+2,s+n+1);
    int tp1 = 2,tp2 = n+1;
    for(int i=3; i<n; i++)
    {
        int u = s[i].second;
        printf("2 %d %d %d\n",1,s[i].second,s[i+1].second); fflush(stdout);
        int x; scanf("%d",&x);
        if(x==-1) {p[--tp2] = s[i].second;}
        else {p[++tp1] = s[i].second;}
    }
    p[++tp1] = s[n].second;
    for(int i=0; i<=n; i++) printf("%d ",p[i]); fflush(stdout);
    return 0;
}

Codeforces 1254C/1255F Point Ordering (交互题)

原文:https://www.cnblogs.com/suncongbo/p/11994646.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!