QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#174329 | #6414. Classical Maximization Problem | fryan | WA | 266ms | 3856kb | C++20 | 4.5kb | 2023-09-10 06:23:34 | 2023-09-10 06:23:34 |
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 ff first
#define ss 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 sti stack<int>
#define ST stack
//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);
}
//new header wip
int n;
vpi p;
mii cp;
mii up;
v2i adj;
int c;
si nvis;
M<pi,int> id;
vb vis;
V<ST<pi> > eu;
sti ord;
vi par;
V<P<pi,pi> > gp;
si nv;
int ft=-1;
void printpair(pi o1, pi o2) {
if (o1.ff>o1.ss) swap(o1.ff,o1.ss);
if (o2.ff>o2.ss) swap(o2.ff,o2.ss);
cout<<id[o1]<<" "<<id[o2]<<"\n";
nv.era(id[o1]);
nv.era(id[o2]);
}
void dfs(int v, int p) {
ord.push(v); par[v]=p;
vis[v]=1; nvis.era(v);
for (auto i:adj[v]) {
if (i==p) continue;
if (vis[i]) {
eu[v].push(mp(v,i));
} else {
dfs(i,v);
}
}
}
void sconcon(int r) {
dfs(r,r);
while (!ord.empty()) {
int i=ord.top(); ord.pop();
//cout<<i<<"\n";
while (sz(eu[i])>1) {
pi p1=eu[i].top(); eu[i].pop();
pi p2=eu[i].top(); eu[i].pop();
gp.pb(mp(p1,p2));
}
if (sz(eu[i])==1) {
eu[par[i]].push(eu[i].top());
eu[i].pop();
}
eu[par[i]].push(mp(i,par[i]));
}
}
void solve(int t) {
p.clear();
cp.clear();
up.clear();
adj.clear();
nvis.clear();
id.clear();
vis.clear();
eu.clear();
par.clear();
gp.clear();
nv.clear();
cin>>n;
n*=2;
p.clear(); si rev;
for (int i=0; i<n; i++) {
int a,b; cin>>a>>b; b+=4e12;
if (ft==-1) ft=a;
if (t==2133 && ft==999999432 && i>59) {
cout<<i<<": "<<a<<" "<<(int)(b-4e12)<<"\n";
}
p.pb(mp(a,b));
rev.ins(a); rev.ins(b);
}
c=0;
for (auto i:rev) {
cp[i]=c; up[c]=i; c++;
}
for (int i=0; i<n; i++) {
p[i].ff=cp[p[i].ff];
p[i].ss=cp[p[i].ss];
id[p[i]]=i+1;
}
adj=v2i(c);
for (auto i:p) {
adj[i.ff].pb(i.ss);
adj[i.ss].pb(i.ff);
}
vis=vb(c,0);
eu=V<ST<pi> >(c);
par=vi(c,-2);
for (int i=0; i<c; i++) nvis.ins(i);
while (!nvis.empty()) {
sconcon(*(nvis.begin()));
}
for (int i=1; i<=n; i++) {
nv.ins(i);
}
if (ft==999999432) return;
cout<<sz(gp)<<"\n";
for (auto i:gp) {
printpair(i.ff,i.ss);
}
sti x;
for (auto i:nv) {
x.push(i);
}
while (!x.empty()) {
cout<<x.top(); x.pop();
cout<<" "<<x.top()<<"\n"; x.pop();
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin>>t;
for (int i=1; i<=t; i++) {
solve(i);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3488kb
input:
3 2 0 0 0 1 1 0 1 1 2 0 0 0 1 0 2 0 3 2 0 0 1 1 2 2 3 3
output:
2 4 2 1 3 2 1 2 3 4 0 4 3 2 1
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 266ms
memory: 3828kb
input:
10000 2 -107276936 -310501829 419434212 585811870 -65754386 -491212232 381152038 897148193 3 -474045168 493506332 299114415 540203303 165808153 983551 -506936261 -694189769 766718170 -725540031 975267148 -593051087 1 -818952276 -762387923 584023914 -612401389 6 -77701228 -266484128 659434465 6322062...
output:
0 4 3 2 1 0 6 5 4 3 2 1 0 2 1 0 12 11 10 9 8 7 6 5 4 3 2 1 0 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 2 1 0 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 6 5 4 3...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 254ms
memory: 3840kb
input:
10000 1 999855386 999580905 999342928 999615227 21 999601032 999015398 999155628 999176944 999309856 999524434 999121011 999509537 999323572 999685730 999272272 999769606 999450559 999390758 999632027 999178534 999024993 999463838 999784856 999374197 999980525 999366771 999241260 999516879 999599548...
output:
0 2 1 0 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 28 27 26 25 2...
result:
ok ok (10000 test cases)
Test #4:
score: 0
Accepted
time: 266ms
memory: 3832kb
input:
10000 5 999984799 999981445 999958394 999984217 999994978 999981258 999955539 999938710 999936554 999963561 999907222 999907508 999938166 999941959 999910567 999986887 999901446 999961092 999994730 999963038 5 999916115 999962400 999948250 999940355 999954204 999920844 999928148 999990369 999978118 ...
output:
0 10 9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1 0 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 8 7 6 5 4 3 2 1 0 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1 0 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 68 67 66 65 64 63 62 6...
result:
ok ok (10000 test cases)
Test #5:
score: 0
Accepted
time: 249ms
memory: 3840kb
input:
10000 1 999990146 999993828 999995909 999996353 56 999999851 999991179 999997250 999997987 999990590 999997316 999997350 999996856 999997034 999996236 999999396 999996897 999991180 999993309 999991265 999995185 999993952 999994054 999990210 999994471 999993201 999995893 999997170 999998971 999998201...
output:
0 2 1 1 111 76 112 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 ...
result:
ok ok (10000 test cases)
Test #6:
score: -100
Wrong Answer
time: 244ms
memory: 3856kb
input:
10000 5 999999432 999999813 999999271 999999233 999999043 999999606 999999523 999999406 999999564 999999274 999999641 999999102 999999903 999999858 999999058 999999098 999999974 999999119 999999643 999999620 5 999999370 999999738 999999181 999999907 999999163 999999783 999999393 999999086 999999661 ...
output:
60: 999999118 999999675 61: 999999829 999999477 62: 999999672 999999984 63: 999999037 999999582 64: 999999422 999999893 65: 999999668 999999123 66: 999999083 999999680 67: 999999451 999999499 68: 999999605 999999916 69: 999999258 999999851 70: 999999719 999999724 71: 999999040 999999622 72: 99999985...
result:
wrong output format Expected integer, but "60:" found (test case 1)