QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61956#4500. LoopqinjianbinAC ✓225ms10908kbC++7.2kb2022-11-16 11:22:422022-11-16 11:22:42

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-16 11:22:42]
  • 评测
  • 测评结果:AC
  • 用时:225ms
  • 内存:10908kb
  • [2022-11-16 11:22:42]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<bitset>
#include<functional>
using namespace std;
//STL库常用(vector, map, set, pair)
#define pii pair<int,int>
#define pdd pair<double,double>
#define F first
#define S second
//常量
#define PI (acos(-1.0))
#define INF 0x3f3f3f3f
//必加
#ifdef TanJI
#include<cassert>
#define dbg(...) do {cerr << #__VA_ARGS__ << " -> "; err(__VA_ARGS__); } while(0)
void err() {cerr << endl;}
template<template<typename...> class T, typename t, typename... A> void err(T<t> a, A... x) {for (auto v: a) cerr << v << ' '; cerr << ", "; err(x...);}
template<typename T, typename... A> void err(T a, A... x) {cerr << a << ' '; err(x...);}
template<typename T> void err(T *a, int len) {for (int i = 0; i < len; i++) cerr << a[i] << ' '; err();}
#else 
#define dbg(...)
#define assert(...)
#endif
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
// 快读快输
template<typename T> inline T read() {T x=0; bool f=0; char c=getchar();while(!isdigit(c)){if(c =='-')f= 1; c=getchar();}while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return f?~x+1:x;}
template<typename T> inline void print(T k){ int num = 0,ch[20]; if(k == 0){ putchar('0'); return ; } (k<0)&&(putchar('-'),k = -k); while(k>0) ch[++num] = k%10, k /= 10; while(num) putchar(ch[num--]+48); }
//图论
const int GRAPHN = 1, GRAPHM = 1;
int h[GRAPHN], e[GRAPHM], ne[GRAPHM], wei[GRAPHM], idx;
void AddEdge(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
void AddEdge(int h[], int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;}
void AddEdge(int h[], int a, int b, int c) {e[idx] = b, ne[idx] = h[a], wei[idx] = c, h[a] = idx++;}
// 数学公式
template<typename T> inline T gcd(T a, T b){ return b==0 ? a : gcd(b,a%b); }
template<typename T> inline T lowbit(T x){ return x&(-x); }
template<typename T> inline bool mishu(T x){ return x>0?(x&(x-1))==0:false; }
template<typename T1,typename T2, typename T3> inline ll q_mul(T1 a,T2 b,T3 p){ ll w = 0; while(b){ if(b&1) w = (w+a)%p; b>>=1; a = (a+a)%p; } return w; }
template<typename T,typename T2> inline ll f_mul(T a,T b,T2 p){ return (a*b - (ll)((long double)a/p*b)*p+p)%p; }
template<typename T1,typename T2, typename T3> inline ll q_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = (w*a)%p; b>>=1; a = (a*a)%p;} return w; }
template<typename T1,typename T2, typename T3> inline ll s_pow(T1 a,T2 b,T3 p){ ll w = 1; while(b){ if(b&1) w = q_mul(w,a,p); b>>=1; a = q_mul(a,a,p);} return w; }
template<typename T> inline ll ex_gcd(T a, T b, T& x, T& y){ if(b == 0){ x = 1, y = 0; return (ll)a; } ll r = ex_gcd(b,a%b,y,x); y -= a/b*x; return r;/*gcd*/ }
template<typename T1,typename T2> inline ll com(T1 m, T2 n) { int k = 1;ll ans = 1; while(k <= n){ ans=((m-k+1)*ans)/k;k++;} return ans; }
template<typename T> inline bool isprime(T n){ if(n <= 3) return n>1; if(n%6 != 1 && n%6 != 5) return 0; T n_s = floor(sqrt((db)(n))); for(int i = 5; i <= n_s; i += 6){ if(n%i == 0 || n%(i+2) == 0) return 0; } return 1; }
/* ----------------------------------------------------------------------------------------------------------------------------------------------------------------- */
// #define DEBUG 1  // 调试开关
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
    IO() : p1(buf), p2(buf), pp(pbuf) {}

    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
#endif
    inline char gc() {
#if DEBUG // 调试,可显示字符
        return getchar();
#endif
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }

    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }

    template <class T>
    inline void read(T &x) {
        register double tmp = 1;
        register bool sign = 0;
        x = 0;
        register char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }

    inline void read(char *s) {
        register char ch = gc();
        for (; blank(ch); ch = gc())
            ;
        for (; !blank(ch); ch = gc())
            *s++ = ch;
        *s = 0;
    }

    inline void read(char &c) {
        for (c = gc(); blank(c); c = gc())
            ;
    }

    inline void push(const char &c) {
#if DEBUG // 调试,可显示字符
        putchar(c);
#else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
#endif
    }

    template <class T>
    inline void write(T x) {
        if (x < 0) x = -x, push('-'); // 负数输出
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top)
            push(sta[--top] + '0');
    }

    template <class T>
    inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;
const int MAXN = 3e5 + 10;

int T, n, k;
int a[MAXN];
struct Node {
    int val, id;
    Node (int val = 0, int id = 0) : val(val), id(id) {}
    bool operator < (const Node &a) const {return val < a.val;}
};

int main() {
#ifdef TanJI
    clock_t c1 = clock();
    freopen("D:\\Cpp\\1.in", "r", stdin);
    freopen("D:\\Cpp\\1.out", "w", stdout);
#endif
//--------------------------------------------
    scanf("%d", &T);
    while (T--) {
        // io.read(n); io.read(k);
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) 
            scanf("%d", &a[i]);
            // io.read(a[i]);   
        priority_queue<Node> que;
        vector<int> vec;
        int r = min(n, k + 1), l = 1;
        while (1) {
            while (l <= r) {
                que.push(Node(a[l], l));
                l++;
            }
            Node tmp = que.top(); que.pop();
            vec.push_back(tmp.val);
            if (tmp.id == r) 
                break;
            if (r != n) r++;
        }
        r++;
        while (r <= n && que.size()) {
            if (a[r] < que.top().val) {
                vec.push_back(que.top().val);
                que.pop();
            }
            else {
                vec.push_back(a[r++]);
            }
        }
        while (r <= n) 
            vec.push_back(a[r++]);
        while (que.size()) {
            vec.push_back(que.top().val);
            que.pop();
        }
        for (int i = 0; i < n; i++) {
            printf("%d%c", vec[i], i != n - 1 ? ' ' : '\n');
        }
    }
//--------------------------------------------    
#ifdef TanJI
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
#endif
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 225ms
memory: 10908kb

input:

100
300000 300000
1 1 300000 153456 153456 1 153456 153456 300000 1 300000 1 300000 300000 300000 1 300000 300000 300000 1 300000 300000 300000 300000 300000 1 300000 153456 300000 1 153456 153456 1 300000 153456 300000 300000 1 300000 1 1 153456 153456 300000 153456 153456 153456 153456 1 300000 30...

output:

300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000 300000...

result:

ok 100 lines