QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #174346 | #6414. Classical Maximization Problem | fryan | Compile Error | / | / | C++20 | 3.7kb | 2023-09-10 06:42:38 | 2023-09-10 06:42:38 |
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>
#pragma GCC optimize ("")
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;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
const int N=401000;
vector<pi> e[N];
int vis[N],x[N],y[N],vise[N];
int n;
vector<pi> ans;
VI ext;
void dfs(int x,int pe) {
vis[x]=1;
for (auto [y,id]:e[x]) {
if (id==pe) continue;
if (!vis[y]) dfs(y,id);
}
VI es;
for (auto [y,id]:e[x]) {
if (id==pe||vise[id]) continue;
es.pb(id);
}
if (SZ(es)%2!=0) es.pb(pe),pe=-1;
for (int i=0;i+1<SZ(es);i+=2) {
if (es[i]!=-1&&es[i+1]!=-1) {
ans.pb({es[i],es[i+1]});
vise[es[i]]=1;
vise[es[i+1]]=1;
} else {
ext.pb(es[i]+es[i+1]+1);
}
}
return;
}
void solve() {
cin>>n;
vector<pi> ps;
ans.clear();
rep(i,0,2*n) {
scanf("%d%d",x+i,y+i);
ps.pb(mp(x[i],0));
ps.pb(mp(y[i],1));
}
sort(all(ps));
ps.erase(unique(all(ps)),ps.end());
int m=SZ(ps);
rep(i,1,m+1) e[i].clear(),vis[i]=0;
rep(i,0,2*n) {
int L=lower_bound(all(ps),mp(x[i],0))-ps.begin()+1;
int R=lower_bound(all(ps),mp(y[i],1))-ps.begin()+1;
e[L].pb(mp(R,i));
e[R].pb(mp(L,i));
//printf("Eg %d %d %d\n",L,R,i);
vise[i]=0;
}
ext.clear();
rep(i,1,m+1) if (!vis[i]) {
dfs(i,-1);
}
printf("%d\n",SZ(ans));
assert(SZ(ext)%2==0);
for (int i=0;i<SZ(ext);i+=2) {
ans.pb({ext[i],ext[i+1]});
}
for (auto [u,v]:ans) printf("%d %d\n",u+1,v+1);
}
int _;
int main() {
for (scanf("%d",&_);_;_--) {
solve();
}
}
Details
answer.code:109: warning: "all" redefined
109 | #define all(x) (x).begin(),(x).end()
|
answer.code:61: note: this is the location of the previous definition
61 | #define all(x) begin(x), end(x)
|
answer.code:47:25: warning: bad option ‘-f’ to pragma ‘optimize’ [-Wpragmas]
47 | #pragma GCC optimize ("")
| ^
answer.code:125:22: warning: bad option ‘-f’ to attribute ‘optimize’ [-Wattributes]
125 | void dfs(int x,int pe) {
| ^
answer.code:149:12: warning: bad option ‘-f’ to attribute ‘optimize’ [-Wattributes]
149 | void solve() {
| ^
answer.code: In function ‘void solve()’:
answer.code:154:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
154 | scanf("%d%d",x+i,y+i);
| ~^ ~~~
| | |
| int* ll* {aka long long int*}
| %lld
answer.code:154:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
154 | scanf("%d%d",x+i,y+i);
| ~^ ~~~
| | |
| int* ll* {aka long long int*}
| %lld
answer.code:174:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
174 | printf("%d\n",SZ(ans));
| ~^
| |
| int
| %lld
answer.code:179:39: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::tuple_element<0, std::pair<long long int, long long int> >::type’ {aka ‘long long int’} [-Wformat=]
179 | for (auto [u,v]:ans) printf("%d %d\n",u+1,v+1);
| ~^ ~~~
| | |
| int std::tuple_element<0, std::pair<long long int, long long int> >::type {aka long long int}
| %lld
answer.code:179:42: warning: format ‘%d’ expects argument of type ‘int’, but argument 3 has type ‘std::tuple_element<1, std::pair<long long int, long long int> >::type’ {aka ‘long long int’} [-Wformat=]
179 | for (auto [u,v]:ans) printf("%d %d\n",u+1,v+1);
| ~^ ~~~
| | |
| int std::tuple_element<1, std::pair<long long int, long long int> >::type {aka long long int}
| %lld
answer.code: At global scope:
answer.code:183:10: warning: bad option ‘-f’ to attribute ‘optimize’ [-Wattributes]
183 | int main() {
| ^
answer.code:52:13: error: ‘::main’ must return ‘int’
52 | #define int ll
| ^~
answer.code:183:1: note: in expansion of macro ‘int’
183 | int main() {
| ^~~
answer.code: In function ‘int main()’:
answer.code:184:22: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
184 | for (scanf("%d",&_);_;_--) {
| ~^ ~~
| | |
| | ll* {aka long long int*}
| int*
| %lld
In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
from /usr/include/c++/11/algorithm:61,
from answer.code:2:
/usr/include/c++/11/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Value = const std::pair<long long int, int>]’:
/usr/include/c++/11/bits/stl_algobase.h:1464:14: required from ‘constexpr _ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<long long int, int>; _Compare = __gnu_cxx::__ops::_Iter_less_val]’
/usr/include/c++/11/bits/stl_algobase.h:1499:32: required from ‘constexpr _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<long long int, long long int>*, std::vector<std::pair<long long int, long long int> > >; _Tp = std::pair<long long int, int>]’
answer.code:163:20: required from here
/usr/include/c++/11/bits/predefined_ops.h:69:22: error: no match f...