CodeForces Gym 100685J Just Another Disney Problem (STL,排序)
2024-08-30 09:32:13
题意:给定你大小未知的n个数,你允许有不超过一万次的询问,每次询问两个数,第i个数是否比第j个数小?然后后台会返回给你一个结果YES或者NO(即一行输入),
然后经过多次询问后,你需要给出一个正确的原未知序列的升序排列。
析:当时是真没看懂题意是啥意思,然后就放过了,如果看懂了,并不是很难么,这不就是一个排序么,你可以问后台要数据,然后你决定怎么排序,
我们只要处理这个排序就好,但是不能用sort进行排序,因为这个的复杂度并总不是nlogn,如果是极端数据就卡不过了,也就是说可能会超过询问10000次,
要么我们自己写个快排要么用stabble_sort,这个排序函数来解决。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a < b ? a : b; }
inline int Max(int a, int b){ return a > b ? a : b; }
inline LL Min(LL a, LL b){ return a < b ? a : b; }
inline LL Max(LL a, LL b){ return a > b ? a : b; }
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
int a[maxn];
string s; bool cmp(int a, int b){
cout << "1 " << a << " " << b << endl;
cin >> s;
return s[0] == 'Y';
} int main(){
cout.flush();
cin >> n;
for(int i = 0; i < n; ++i) a[i] = i+1;
stable_sort(a, a+n, cmp);
cout << "0";
for(int i = 0; i < n; ++i) cout << " " << a[i];
cout << endl;
return 0;
}
最新文章
- 微信支付 发布后显示 System:access_denied
- EMF学习,为了实现可扩展可自定义的模型验证 - 各种实现方法学习
- redis + 主从 + 持久化 + 分片 + 集群 + spring集成
- LINUX总结
- js页面刷新之实现普通页面
- 项目使用中Linq使用总结
- SqlServer int型转varchar型 出现*号
- 该如何理解AMD ,CMD,CommonJS规范--javascript模块化加载学习总结
- 学习笔记-Kuaihu(仿知乎日报)
- Android之网络编程
- java 获取数组(二维数组)长度实例程序
- Java中重写与重载的辨析
- Git for Windows
- Android 解析内存泄漏
- 基于MMSeg算法的中文分词类库
- Codeforces Round#310 div2
- 两个port贴合七夕主题,百度输入法的“情感营销”策略
- JAVA入门[3]—Spring依赖注入
- Swift下多个Storyboard的项目结构
- 记阿里云SLB后配置Nginx反向代理百度地图API的坑
热门文章
- UVA 10526 - Intellectual Property (后缀数组)
- inception安装步骤---自己整理的安装步骤
- 多媒体开发之---h.264 SPS PPS解析源代码,C实现一以及nal分析器
- eclipse中怎么删除重复的console
- SVN在myeclipse中新建地址的时出现被拒绝
- swift-ios开发pod的使用(1)
- SpringSecurity加密Salt
- MT6737 Android N 平台 Audio系统学习----录音到播放录音流程分析
- 关于<;context:annotation-config/>;配置
- sendevent是使用