QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#651268#4776. Smoking gunSGColinWA 39ms4108kbC++202.1kb2024-10-18 17:33:492024-10-18 17:33:50

Judging History

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

  • [2024-10-18 17:33:50]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:4108kb
  • [2024-10-18 17:33:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 107;

double t[N][N], dis[N][N];

bool use[N];

inline void work() {
    int n, m;
    cin >> n >> m;
    vector<string> nam; nam.eb("");
    map<string, int> id;
    vector<pii> cor(n + 1);
    vector<int> fires;
    rep(i, 1, n) {
        string str; cin >> str;
        id[str] = i;
        nam.eb(str);
        use[i] = false;
        int x, y; cin >> x >> y;
        cor[i] = {x, y};
    }
    rep(i, 1, n) rep(j, 1, n) {
        t[i][j] = (i == j ? 0 : 1e18);
        auto [x1, y1] = cor[i];
        auto [x2, y2] = cor[j];
        dis[i][j] = sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
    }
    rep(i, 1, m) {
        string str; cin >> str; while (str == "") cin >> str;
        int a = id[str];
        cin >> str; cin >> str;
        int b = id[str];
        cin >> str; cin >> str; cin >> str;
        int c = id[str];
        double dif = (dis[c][a] - dis[b][a]) / 340;
        t[c][b] = min(t[c][b], dif);
        fires.eb(b);
        fires.eb(c);
    }
    sort(all(fires));
    fires.erase(unique(all(fires)), fires.end());
    rep(k, 1, n) rep(i, 1, n) rep(j, 1, n) t[i][j] = min(t[i][j], t[i][k] + t[k][j]);
    rep(i, 1, n) if (t[i][i] < 0) {puts("IMPOSSIBLE"); return;}
    vector<string> ans;
    rep(turn, 1, fires.size()) {
        int id = 0;
        for (auto j : fires) if (!use[j]) {
            bool fl = true;
            for (auto k : fires)
                if (!use[k] && k != j && t[k][j] > 0) {fl = false; break;}
            if (fl) {id = j; break;}
        }
        if (id) {ans.eb(nam[id]); use[id] = true;}
        else {puts("UNKNOWN"); return;}
    }
    for (auto x : ans) cout << x << " ";
    cout << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) work();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3620kb

input:

3
4 2
BillyTheKid 0 0
Andy 10 0
John 19 0
Larry 20 0
Andy heard BillyTheKid firing before John
Larry heard John firing before BillyTheKid
2 2
Andy 0 0
Beate 0 1
Andy heard Beate firing before Andy
Beate heard Andy firing before Beate
3 1
Andy 0 0
Beate 0 1
Charles 1 3
Beate heard Andy firing before ...

output:

BillyTheKid John 
IMPOSSIBLE
UNKNOWN

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 39ms
memory: 4108kb

input:

100
3 2
A 9 3
B 9 9
C 0 0
C heard A firing before B
A heard B firing before A
4 3
A 0 0
B 10 0
C 10 1
D 5 1
B heard A firing before B
B heard B firing before C
D heard C firing before A
3 1
A 0 0
B 0 1
C 1000000 0
C heard A firing before B
4 2
A 0 0
B 0 1
C 1000000 0
D 500000 0
C heard A firing befo...

output:

B A 
SHTab SHTac SHTaa 
ag ah aj ac ab ae aa ad ai 
ab ai 
ai ab ad ac ae aa ah 
ad ah ai af aa 
ab ar ah al ao ac an aa aq af at ae aj ai ap ag am 
ac ar ak ao aa ag ae aq an ai 
at as ae ac 
ah ai ag am ad an ap ae af as ak ar aa ac ao at 
ad ah 
ak ba ai af aj aq ax ar ad ae ap am 
ag aq au aj 
a...

result:

wrong answer 1st lines differ - expected: 'IMPOSSIBLE', found: 'B A '