QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#294846	#4829. Mark on a Graph	ucup-team055^#	0	414ms	4032kb	C++23	2.2kb	2023-12-30 16:57:12	2023-12-30 16:57:12

Judging History

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

[2023-12-30 16:57:12]
评测

测评结果：0
用时：414ms
内存：4032kb

查看

[2023-12-30 16:57:12]
提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }


mt19937 rnd(169);
int main() {
//    cin.tie(0)->sync_with_stdio(0);
    
    ll lo = -300, hi = -180;
    ll ans = (lo * 3 + hi * 2) / 5;
    cerr << ans << endl;
    
    ll N, M;
    cin >> N >> M;
    
    vector g(N, vector<ll>{});
    rep(i, 0, M) {
        ll A, B;
        cin >> A >> B;
        A--; B--;
        g[A].push_back(B);
        g[B].push_back(A);
    }
    
    vector<ll> deg(N);
    rep(i, 0, N) deg[i] = g[i].size();
    ranges::sort(deg, greater<>{});
    deg.resize(6);
    
    rep(i, 0, size(deg)) cerr << deg[i] << " \n"[i + 1 == size(deg)];
    rep(_, 0, 10000) {
        vector<ll> d(N);
        rep(m, 0, M * 2) d[rnd() % N]++;
        
        vector<ll> cnt(M * 2 + 1);
        for(ll x : d) cnt[x]++;
        
        vector<ll> A, B;
        [&]{
            for(ll i = size(cnt); i--; ) rep(_, 0, cnt[i]) {
                A.push_back(i);
                if(A.size() == 6) return;
            }
        }();
        
        if(deg <= A) {
            ans++;
            continue;
        }
        
        A[0] += 5;
        rep(i, 1, 6) A[i]++;
        
        if(A <= deg) ans--;
    }
    
    cerr << ans << endl;
    
    if(ans < 0) {
        puts("ok");
        return 0;
    }
    
    puts("mark");
    puts("5");
    vector<ll> idx(N);
    rep(i, 0, N) idx[i] = i;
    
    auto add_edge = [&](ll i, ll j) -> bool {
        if(i == j) return 0;
        if(ranges::count(g[i], j)) return 0;
        g[i].push_back(j);
        g[j].push_back(i);
        
        cout << i + 1 << ' ' << j + 1 << endl;
        return 1;
    };
    
    rep(_, 0, 5) {
        ranges::shuffle(idx, rnd);
        ranges::sort(idx, greater<>{}, [&](ll i) { return g[i].size(); });
        rep(j, 1, N) if(add_edge(idx[0], idx[j])) break;
    }
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 295ms

memory: 3772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 159ms

memory: 3916kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 414ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 266ms

memory: 3988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 268ms

memory: 3800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 240ms

memory: 3752kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 241ms

memory: 3772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 360ms

memory: 4032kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 370ms

memory: 3828kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 331ms

memory: 3836kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 261ms

memory: 3788kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 278ms

memory: 3772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 170ms

memory: 3652kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 248ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 217ms

memory: 3964kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 232ms

memory: 3968kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 231ms

memory: 3764kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 374ms

memory: 4016kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 291ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 326ms

memory: 3772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 286ms

memory: 3768kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 258ms

memory: 3928kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 272ms

memory: 3812kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 195ms

memory: 3716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 339ms

memory: 4012kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 304ms

memory: 3812kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 256ms

memory: 3920kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 343ms

memory: 4024kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 245ms

memory: 3988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 327ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 252ms

memory: 3772kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 304ms

memory: 3800kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 376ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 161ms

memory: 3688kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 164ms

memory: 3716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 161ms

memory: 3716kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 166ms

memory: 3724kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 171ms

memory: 3736kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 161ms

memory: 3880kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 175ms

memory: 3920kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 165ms

memory: 3708kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 166ms

memory: 3880kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 189ms

memory: 3660kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 161ms

memory: 3728kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 0

Wrong Answer on the first run

input:

output:

ok

input:

output:

result:

wrong answer Token "ok" doesn't correspond to pattern "mark"