QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185648 | #6561. Fail Fast | fryan | WA | 250ms | 22988kb | C++14 | 4.0kb | 2023-09-22 13:57:05 | 2023-09-22 13:57:06 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <immintrin.h>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <variant>
using namespace std;
//numbers
using ll=long long;
#define int ll
using ld=long double;
//pairs
#define P pair
#define pi P<int,int>
#define f first
#define s second
#define mp make_pair
//std data structure
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
//vectors
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vsi V<si>
#define vb V<bool>
#define pb push_back
//sets
#define S set
#define MS multiset
#define US unordered_set
#define si S<int>
#define msi MS<int>
#define usi US<int>
#define ins insert
#define era erase
//maps
#define M map
#define UM unordered_map
#define mii M<int,int>
#define mivi UM<int,vi>
#define misi UM<int,si>
#define umii UM<int,int>
#define umivi UM<int,vi>
#define umisi UM<int,si>
//queues
#define Q queue
#define PQ priority_queue
#define qi Q<int>
#define qpi Q<pi>
#define pqi PQ<int>
#define rpqi PQ<int,vi,greater<int> >
#define pqpi PQ<pi>
#define rpqpi PQ<pi,vpi,greater<pi> >
#define pp P<ld, P< P<ld,ld>, pi > >
//constants
const int MOD=998244353;
const int INF=922337203685477580;
//nt functions
int binpow(int a, int b, int m=MOD) {
a%=m; int res=1;
while (b>0) {
if (b&1) res=res*a%m;
a=a*a%m;
b>>=1;
}
return res;
}
int gcd (int a, int b) {
return b?gcd (b,a%b):a;
}
int lcm (int a, int b) {
return a/gcd(a,b)*b;
}
int inv(int i, int m=MOD) {
return binpow(i, m-2, m);
}
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) {x = get(x), y = get(y);if (x == y) return false;if (e[x] > e[y]) swap(x, y);e[x] += e[y]; e[y] = x;return true;}
};
struct ccpp {
bool operator() (pp o1, pp o2) {
return true;
}
};
ld calc(P<ld,ld> x) {
ld ret=x.f/((ld)1-x.s); return ret;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n; cin>>n;
V<pp> ts(n+1);
for (int i=1; i<=n; i++) {
cin>>ts[i].s.f.f>>ts[i].s.f.s>>ts[i].s.s.f;
ts[i].s.s.s=i; ts[i].f=calc(ts[i].s.f);
}
vi bk(n+1,0);
vi bk2(n+1,0);
vb vis(n+1,0);
DSU dsu(n+1);
S<pp> ord;
for (int i=1; i<=n; i++) {
ord.ins(ts[i]);
bk[i]=i; bk2[i]=i;
}
/*for (int i=1; i<=n; i++) {
cout<<ts[i].f<<" "<<ts[i].s.f.f<<" "<<ts[i].s.f.s<<"\n";
}
cout<<"--------\n";*/
while (!ord.empty()) {
pp t=*(ord.begin()); ord.era(t);
ld c=t.s.f.f; ld p=t.s.f.s;
int d=t.s.s.f; int i=t.s.s.s;
// cout<<c<<" "<<p<<" "<<d<<" "<<i<<"\n";
if (d==0 || vis[d]) {
int cp=i;
while (!vis[cp]) {
vis[cp]=1;
cout<<cp<<"\n";
cp=bk[cp];
}
continue;
}
bk[bk2[dsu.get(d)]]=i;
bk2[dsu.get(d)]=bk2[dsu.get(i)];
dsu.unite(i,d);
pp nd;
ord.era(ts[d]);
nd.s.f.f=ts[d].s.f.f+ts[d].s.f.s*c;
nd.s.f.s=ts[d].s.f.s*p;
nd.f=calc(nd.s.f);
nd.s.s.f=ts[d].s.s.f;
nd.s.s.s=ts[d].s.s.s;
ts[d]=nd;
ord.ins(nd);
}
/*for (int i=1; i<=n; i++) {
cout<<ts[i].f<<" "<<ts[i].s.f.f<<" "<<ts[i].s.f.s<<"\n";
}*/
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
4 100 0.5 0 200 0.1 1 10 0.5 2 10 0.9 0
output:
4 1 2 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 84 0.716 0 91 0.115 0 19 0.640 1 103 0.455 0
output:
2 1 3 4
result:
ok correct
Test #3:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
10 18 0.574073 0 13 0.540309 0 13 0.539018 2 12 0.572910 2 15 0.570616 4 16 0.510215 3 17 0.504083 5 19 0.539297 1 19 0.577271 7 10 0.578346 1
output:
2 4 3 6 5 7 1 10 8 9
result:
ok correct
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
20 93 0.093030 0 53 0.056639 0 39 0.021549 0 48 0.069268 3 58 0.009572 4 22 0.015083 1 27 0.024351 5 68 0.085055 7 48 0.031563 5 46 0.025067 9 15 0.095445 2 57 0.011233 6 97 0.028239 2 8 0.060758 6 59 0.097330 13 34 0.052120 3 73 0.055127 11 53 0.004135 12 24 0.051183 5 56 0.027001 13
output:
3 16 4 2 11 5 19 7 9 10 8 17 1 6 14 12 18 13 20 15
result:
ok correct
Test #5:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
20 971329 0.076234 0 996879 0.012978 0 994191 0.056803 0 978400 0.080792 1 907508 0.008858 4 992071 0.057419 2 901661 0.089621 6 912521 0.051943 5 979169 0.040201 5 904759 0.083405 7 928478 0.092658 7 980034 0.054747 3 906344 0.053231 10 907474 0.090196 8 927695 0.023153 4 995464 0.009387 2 984650 0...
output:
2 16 6 7 10 13 17 19 20 11 1 4 5 15 8 14 18 9 3 12
result:
ok correct
Test #6:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
20 54 0.952741 0 41 0.912397 0 11 0.963309 0 66 0.915806 3 47 0.919191 4 51 0.906473 5 24 0.989650 6 97 0.964070 7 56 0.997215 1 39 0.981950 2 50 0.994037 2 92 0.942000 7 97 0.900405 3 53 0.950071 6 16 0.980631 14 63 0.950876 10 49 0.995183 15 20 0.908520 5 71 0.949757 16 76 0.972330 9
output:
3 2 4 5 18 6 13 14 15 1 10 16 19 7 12 8 9 20 11 17
result:
ok correct
Test #7:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
20 933154 0.904059 0 929160 0.911627 0 999437 0.921760 0 991335 0.904136 1 903530 0.943148 4 904464 0.921035 2 944382 0.912394 6 990971 0.982189 7 941308 0.959290 4 993916 0.945081 7 924496 0.989350 1 938782 0.958578 4 964442 0.997198 11 964358 0.938647 10 911972 0.943888 5 975140 0.993873 4 995611 ...
output:
1 4 2 6 7 3 5 15 10 14 20 12 19 9 11 13 17 8 18 16
result:
ok correct
Test #8:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
1 10 0.5 0
output:
1
result:
ok correct
Test #9:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
2 100 0.8 0 200 0.7 0
output:
1 2
result:
ok correct
Test #10:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2 10 0.5 0 5 0.4 1
output:
1 2
result:
ok correct
Test #11:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2 1000 0.7 2 1 0.6 0
output:
2 1
result:
ok correct
Test #12:
score: 0
Accepted
time: 250ms
memory: 22844kb
input:
100000 938188 0.740681 0 575610 0.965656 1 937341 0.842524 2 817797 0.945396 3 602563 0.818956 4 893939 0.900203 5 952148 0.810399 6 538333 0.960769 7 550079 0.908188 8 676338 0.795726 9 546675 0.529045 10 542108 0.581119 11 963201 0.665127 12 564484 0.897025 13 504952 0.844118 14 673675 0.777947 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #13:
score: 0
Accepted
time: 57ms
memory: 22988kb
input:
100000 501234 0.500516 0 501214 0.503354 1 501013 0.504058 2 502546 0.502962 3 500273 0.505433 4 500197 0.505874 5 505941 0.500204 6 500455 0.506393 7 506433 0.500626 8 503652 0.503861 9 500935 0.507151 10 501370 0.506725 11 502595 0.506236 12 503444 0.505698 13 501723 0.508031 14 505738 0.504150 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #14:
score: 0
Accepted
time: 132ms
memory: 22796kb
input:
100000 768956 0.999996 0 686063 0.999982 1 817790 0.999964 2 897069 0.999958 3 940413 0.999956 4 879098 0.999957 5 687880 0.999964 6 663602 0.999959 7 816976 0.999944 8 572136 0.999958 9 653227 0.999946 10 972448 0.999914 11 836815 0.999920 12 617305 0.999941 13 934633 0.999903 14 757071 0.999917 15...
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
result:
ok correct
Test #15:
score: 0
Accepted
time: 142ms
memory: 22872kb
input:
100000 686602 0.755750 0 606835 0.951986 0 713656 0.504635 0 609527 0.663061 0 752558 0.613758 0 997011 0.880758 0 905135 0.574450 0 732880 0.774286 0 573515 0.609711 0 899010 0.630653 0 664787 0.949029 0 649162 0.965284 0 582075 0.957310 0 939848 0.848816 0 743139 0.738017 0 577134 0.723893 0 91476...
output:
253 67 161 137 179 1001 287 255 3403 97013 304 33 428 135 212 344 237 110 234 35 149 2447 65686 7360 281 267 357 235 11969 10350 55117 23101 44394 90 345 32287 94695 21214 188 5602 3 12430 219 17907 55 71206 152 87789 70 305 9 90656 238 210 5552 72776 32 6029 60929 205 236 6216 249 2763 5064 1136 64...
result:
ok correct
Test #16:
score: -100
Wrong Answer
time: 136ms
memory: 22856kb
input:
100000 866461 0.563475 0 566909 0.892585 1 794999 0.608805 1 572103 0.501998 1 889513 0.669248 4 712553 0.620050 3 721255 0.898776 3 731219 0.870250 5 958886 0.933100 5 946557 0.758386 1 829823 0.901169 6 513249 0.679404 6 707379 0.965023 2 686267 0.691424 13 790432 0.772695 3 630098 0.867609 11 975...
output:
1 4 255 1463 17335 2114 14926 17157 19416 25749 33301 67686 25657 190 2096 37605 50425 2 43930 34070 382 35 1243 11751 70 4349 739 5234 2679 10128 14274 10413 30407 49724 94468 92693 98817 28424 41338 220 4584 702 10034 40074 1056 79762 2754 5745 5840 61325 61426 32441 3 6 12 9550 123 1113 15255 265...
result:
wrong answer your plan is not optimal