QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96502#5154. ETAIsaacMoris#WA 8ms3460kbC++141.5kb2023-04-13 23:20:242023-04-13 23:20:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 23:20:26]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3460kb
  • [2023-04-13 23:20:24]
  • 提交

answer

#include<iostream>
#include <bits/stdc++.h>

# define ld  long double
#define ll long long
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e6 + 5, mod = 998244353, M = 17;

int a, b;

bool good(ll sum, ll base) {
    // sum / base >= a/b
    return sum * b >= a * base;
}

void getInput() {
    string s;
    cin >> s;
    bool f = false;
    for (auto i: s) {
        if (i == '/')f = true;
        else {
            if (!f) a = a * 10 + i - '0';
            else b = b * 10 + i - '0';
        }
    }
}

void doWork() {
    getInput();
  
    int g = __gcd(a, b);
    a /= g;
    b /= g;
    int lvl = 2000;
    vector<int> cnt(lvl + 1, 1);
    cnt.back() = 3000 / b * b - lvl;
    ll sum = (lvl - 1) * (lvl - 2) / 2 + lvl * cnt.back();
    ll base = 3000 / b * b;
    for (int i = cnt.size() - 1; i >= 2; i--) {
        while (cnt[i] && good(sum - 1, base)) {
            cnt[i]--;
            cnt[i - 1]++;
            sum--;
        }
    }
    if (sum * b != a * base) {
        cout << "impossible";
        return;
    }
    cout << base << " " << base - 1 << "\n";
    int last = 1;
    for (int i = 1; i < cnt.size(); i++) {
        for (int j = 1; j <= cnt[i]; j++) {
            cout << last << " " << last + j << "\n";
        }
        last += cnt[i];
    }
}

int main() {
    IO
    int t = 1;
    //  cin >> t;
    for (int i = 1; i <= t; i++) {
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 8ms
memory: 3460kb

input:

1/2

output:

3000 2999
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 6...

result:

FAIL Wrong average distance, got 3499/3000, wanted 1/2