QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#600225#9223. Data DeterminationFlowRays#WA 119ms23712kbC++239.1kb2024-09-29 15:24:062024-09-29 15:24:11

Judging History

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

  • [2024-09-29 15:24:11]
  • 评测
  • 测评结果：WA
  • 用时：119ms
  • 内存：23712kb
查看
  • [2024-09-29 15:24:06]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ve vector

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vpi = vector<vector<pii>>;

const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 2e5+10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define FIO 
struct IO { 
    #ifdef FIO 
        const static int BUFSIZE = 1 << 20; char buf[BUFSIZE], obuf[BUFSIZE], *p1, *p2, *pp; inline char getchar() { return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++); } inline void putchar(char x) { ((pp - obuf == BUFSIZE && (fwrite(obuf, 1, BUFSIZE, stdout), pp = obuf)), *pp = x, pp++); } inline IO &flush() { fwrite(obuf, 1, pp - obuf, stdout); fflush(stdout); return *this; } IO() { p1 = buf, p2 = buf, pp = obuf; } ~IO() { flush(); } 
    #else 
        int (*getchar)() = &::getchar; int (*putchar)(int) = &::putchar; inline IO &flush() { fflush(stdout); return *this; }; 
    #endif 
        string sep = " "; int k = 2; template <typename T, typename std::enable_if<std::is_integral<T>::value || std::is_same<T, __int128_t>::value>::type * = nullptr> inline int r(T &s) { int f = 1; char ch = getchar(); s = 0; while (!isdigit(ch) && ch != EOF) f = (ch == '-' ? -1 : 1), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); s *= f; return ch != EOF; } template <typename T> inline bool r(vector<T> &v) { bool f = true; for(auto &x: v) f &= r(x); return f; } template <typename T> inline bool rv(vector<T> &v, int x = 1) { bool f = true; for (int i = x; i < v.size(); ++i) f &= r(v[i]); return f; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline int r(T &s) { int f = 1; char ch = getchar(); s = 0; while (!isdigit(ch) && ch != EOF && ch != '.') f = (ch == '-' ? -1 : 1), ch = getchar(); while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar(); if (ch == EOF) return false; if (ch == '.') { T eps = 0.1; ch = getchar(); while (isdigit(ch)) s = s + (ch ^ 48) * eps, ch = getchar(), eps /= 10; } s *= f; return ch != EOF; } inline int r(char &c) { char ch = getchar(); c = EOF; while (isspace(ch) && ch != EOF) ch = getchar(); if (ch != EOF) c = ch; return c != EOF; } inline int r(char *c) { char ch = getchar(), *s = c; while (isspace(ch) && ch != EOF) ch = getchar(); while (!isspace(ch) && ch != EOF) *(c++) = ch, ch = getchar(); *c = '\0'; return s != c; } inline int r(string &s) { s.clear(); char ch = getchar(); while (isspace(ch) && ch != EOF) ch = getchar(); while (!isspace(ch) && ch != EOF) s += ch, ch = getchar(); return s.size() > 0; } inline int getline(char *c, const char &ed = '\n') { char ch = getchar(), *s = c; while (ch != ed && ch != EOF) *(c++) = ch, ch = getchar(); *c = '\0'; return s != c; } inline int getline(string &s, const char &ed = '\n') { s.clear(); char ch = getchar(); while (ch != ed && ch != EOF) s += ch, ch = getchar(); return s.size() > 0; } template <typename T = int> inline T r() { T x; r(x); return x; } template <typename T, typename... Ts> int r(T &x, Ts &...val) { return r(x) && r(val...); } template <typename T, typename enable_if<is_integral<T>::value>::type * = nullptr> IO &w(T x) { if (x < 0) putchar('-'), x = -x; static char sta[20]; int top = 0; do sta[top++] = x % 10 + '0', x /= 10; while (x); while (top) putchar(sta[--top]); return *this; } inline IO &w(const string &str) { for (char ch : str) putchar(ch); return *this; } inline IO &w(const char *str) { while (*str != '\0') putchar(*(str++)); return *this; } inline IO &w(char *str) { return w((const char *)str); } inline IO &w(const char &ch) { return putchar(ch), *this; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline IO &w(T x) { if (x > 1e18 || x < -1e18) { w("[Floating point overflow]"); throw; } if (x < 0) putchar('-'), x = -x; const static long long pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 100000000000000000, 100000000000000000}; const auto &n = pow10[k]; long long whole = (int)x; double tmp = (x - whole) * n; long long frac = tmp; double diff = tmp - frac; if (diff > 0.5) { ++frac; if (frac >= n) frac = 0, ++whole; } else if (diff == 0.5 && ((frac == 0U) || (frac & 1U))) ++frac; w(whole); if (k == 0U) { diff = x - (double)whole; if ((!(diff < 0.5) || (diff > 0.5)) && (whole & 1)) ++whole; } else { putchar('.'); static char sta[20]; int count = k, top = 0; while (frac) { sta[top++] = frac % 10 + '0'; frac /= 10, count--; } while (count--) putchar('0'); while (top) putchar(sta[--top]); } return *this; } template <typename T> inline IO &w(vector<T> &v) { bool f = true; for(auto x: v) { if (f) f = false; else w(sep); w(x); }; return *this; } template <typename T> inline IO &wv(vector<T> &v,int x = 1) { bool f = true; for (int i = x; i < v.size(); ++i) { if (f) f = false; else w(sep); w(v[i]); }; wl(); return *this; } template <typename T, typename... Ts> inline IO &w(T x, Ts... val) { w(x); w(sep); w(val...); return *this; } template <typename... Ts> inline IO &wl(Ts... val) { w(val...); putchar('\n'); return *this; } inline IO &wl(void) { putchar('\n'); return *this; } template <typename T> inline IO &ww(T x, const string &s = " ") { w(x), w(s); return *this; } inline IO &ss(const string &s) { return sep = s, *this; } inline IO &sp(const int &K) { return k = K, *this; } 
} io;

struct ER { 
    #define debug(x...) cerr << "Line " << __LINE__ << ": " #x " = "; er.wl(x) 
    #define debug_assert(a, x...) if (not(a)) { cerr << "Line " << __LINE__ << ": Assertion `" #a "` failed." << endl; cerr << #x " = "; er.wl(x); exit(0);} 
    string sep = " "; template <typename T, typename enable_if<is_integral<T>::value>::type * = nullptr> ER &w(T x) { cerr << x; return *this; } inline ER &w(const string &str) { cerr << str; return *this; } inline ER &w(const char *str) { cerr << str; return *this; } inline ER &w(char *str) { return w((const char *)str); } inline ER &w(const char &ch) { cerr << ch; return *this; } template <typename T, typename enable_if<is_floating_point<T>::value>::type * = nullptr> inline ER &w(T x) { cerr << x; return *this; } template <typename A, typename B> inline ER &w(pair<A, B> x) { cerr << "("; w(x.fi); cerr << ", "; w(x.se); cerr << ")"; return *this; } template <typename T, size_t N> inline ER &w(array<T, N> &a) { cerr << "["; bool first = true; for (auto &v : a) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "]"; return *this; } template <typename T> inline ER &w(vector<T> &x) { cerr << "["; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "]"; return *this; } template <typename T, class Cmp> inline ER &w(set<T, Cmp> &x) { cerr << "{"; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "}"; return *this; } template <typename T, class Cmp> inline ER &w(multiset<T, Cmp> &x) { cerr << "{"; bool first = true; for (auto &v : x) { cerr << (first ? "" : ", "); w(v); first = 0; } cerr << "}"; return *this; } template <typename A, typename B, class Cmp> inline ER &w(map<A, B, Cmp> &x) { cerr << "{"; bool first = true; for (auto &[a, b] : x) { cerr << (first ? "" : ", "); w(a); cerr << ": "; w(b); first = 0; } cerr << "}"; return *this; } template <typename T, typename... Ts> inline ER &w(T x, Ts... val) { w(x); w(sep); w(val...); return *this; } template <typename... Ts> inline ER &wl(Ts... val) { w(val...); cerr << endl; return *this; } inline ER &wl(void) { cerr << endl; return *this; } template <typename T> inline ER &ww(T x, const string &s = " ") { w(x), w(s); return *this; } inline ER &ss(const string &s) { return sep = s, *this; } inline ER &sp(const int &K) { cerr << fixed << setprecision(K); return *this; } 
} er;

void solve(){
    int n,k,m;
    io.r(n,k,m);
    vi a(n);
    io.r(a);
    sort(all(a));
    map<int,int> mp;
    forn(i,n) if(!mp.count(a[i])) mp[a[i]] = i;
    if(k%2) {
        if(mp.count(m)) {
            int p = mp[m];
            if(p >= k/2 && n-p-1 >= k/2) {
                io.wl("TAK");
            } else {
                io.wl("NIE");
            }
        } else {
            io.wl("NIE");
        }
    } else {
        set<pii> st;
        forn(i,n) st.insert({a[i],i});
        forn(i,n) {
            int x = 2*m-a[i];
            auto it = st.upper_bound({x,i});
            if(it != st.end()) {
                auto [y,j] = *it;
                if(y == x) {
                    if(i >= k/2-1 && n-j-1 >= k/2-1) {
                        io.wl("TAK");
                        return;
                    }
                }
            }
        }
        io.wl("NIE");
    }

}

int main() {
    int tt;
    io.r(tt);
    while (tt--) {
        solve();
    }

    return 0;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

3
6 4 42
41 43 41 57 41 42
4 2 4
1 2 5 8
7 5 57
101 2 42 5 57 7 13

output:

TAK
NIE
NIE

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 119ms
memory: 23712kb

input:

1
200000 2 482043846
410684388 380438852 309193412 468460689 586281084 680820569 266819813 639025900 488292166 503516930 532292185 618277661 728546481 628339224 673945619 471325257 372807753 325778059 372151033 548358519 276494019 336701079 320784795 377493322 385262271 621712987 349634764 668994576...

output:

NIE

result:

ok single line: 'NIE'

Test #3:

score: 0
Accepted
time: 49ms
memory: 6408kb

input:

10
20000 3530 502140211
367996343 553577602 581694419 435810361 532394401 431613294 485360190 608191058 506969937 531905607 429252296 360241499 519031654 250454430 478548102 753825992 450326073 603766643 566036856 511634983 416622101 753825992 753825992 380511285 390746506 436237616 342529443 878920...

output:

NIE
TAK
TAK
NIE
TAK
NIE
NIE
NIE
NIE
NIE

result:

ok 10 lines

Test #4:

score: 0
Accepted
time: 45ms
memory: 6588kb

input:

10
20000 6 569116309
533654855 569116308 512534907 569116310 500238175 562175605 569116308 569116310 489499020 543748669 569116309 526641247 511510060 504576222 569116309 569116310 569116308 569116310 569116309 569116308 569116309 569116310 569116308 569116310 569116309 569116308 465300463 569116308...

output:

TAK
TAK
NIE
NIE
NIE
NIE
NIE
TAK
NIE
TAK

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 35ms
memory: 9844kb

input:

1
200000 99999 519401084
60561374 111262859 724696443 994449169 60561374 44352999 44352999 994449169 333890219 44352999 326562388 994449169 60561374 994449169 111262859 614556033 60561374 994449169 60561374 994449169 44352999 994449169 60561374 335786619 994449169 994449169 629087444 44352999 464308...

output:

TAK

result:

ok single line: 'TAK'

Test #6:

score: 0
Accepted
time: 22ms
memory: 4604kb

input:

10000
20 4 803793916
803793916 803793916 829654242 823538042 845455104 810621895 828304843 832321738 852423770 843342850 807940523 803793916 852745476 848104693 805326240 842124638 854328280 846662656 851682131 821969928
20 6 500022430
627268122 349233632 48722 48722 85853795 617231525 67926484 2957...

output:

TAK
NIE
NIE
NIE
NIE
TAK
NIE
NIE
NIE
NIE
NIE
TAK
TAK
NIE
TAK
NIE
TAK
NIE
NIE
NIE
TAK
NIE
TAK
NIE
TAK
NIE
NIE
NIE
NIE
TAK
TAK
TAK
TAK
TAK
TAK
NIE
NIE
TAK
NIE
NIE
NIE
TAK
NIE
TAK
NIE
TAK
NIE
NIE
NIE
NIE
TAK
NIE
TAK
NIE
TAK
NIE
TAK
TAK
NIE
TAK
NIE
NIE
NIE
TAK
TAK
NIE
TAK
TAK
NIE
NIE
NIE
TAK
TAK
TAK
NIE
...

result:

ok 10000 lines

Test #7:

score: -100
Wrong Answer
time: 4ms
memory: 4316kb

input:

9009
6 1 497997812
497997809 497997809 497997810 497997811 497997814 497997815
6 4 670159867
670159866 670159867 670159868 670159869 670159869 670159869
6 3 253555654
253555652 253555652 253555655 253555655 253555657 253555657
5 4 58025801
58025798 58025798 58025801 58025801 58025804
6 6 485459580
4...

output:

NIE
NIE
NIE
TAK
NIE
TAK
NIE
NIE
NIE
TAK
NIE
NIE
NIE
NIE
NIE
TAK
NIE
NIE
TAK
TAK
NIE
NIE
NIE
NIE
NIE
TAK
NIE
TAK
TAK
TAK
NIE
TAK
TAK
NIE
TAK
TAK
TAK
NIE
NIE
NIE
NIE
TAK
NIE
NIE
NIE
NIE
TAK
TAK
NIE
NIE
NIE
TAK
NIE
NIE
NIE
TAK
NIE
NIE
NIE
TAK
NIE
TAK
NIE
NIE
TAK
NIE
NIE
TAK
TAK
NIE
NIE
NIE
TAK
TAK
TAK
...

result:

wrong answer 39th lines differ - expected: 'TAK', found: 'NIE'
English 繁體中文 简体中文

伺服器時間: 2024-12-04 18:02:19 | 開源專案