QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #174349 | #6414. Classical Maximization Problem | fryan | Compile Error | / | / | C++20 | 3.9kb | 2023-09-10 06:45:17 | 2023-09-10 06:45:17 |
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> >
//constants
const int MOD=998244353;
const int INF=922337203685477580;
using namespace std;
#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;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=401000;
vector<PII> e[N];
int vis[N],x[N],y[N],vise[N];
int n;
vector<PII> 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() {
scanf("%d",&n);
vector<PII> 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 _;
signed main() {
for (scanf("%d",&_);_;_--) {
solve();
}
}
Details
answer.code:107: warning: "all" redefined
107 | #define all(x) (x).begin(),(x).end()
|
answer.code:60: note: this is the location of the previous definition
60 | #define all(x) begin(x), end(x)
|
answer.code: In function ‘void solve()’:
answer.code:155:17: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
155 | scanf("%d",&n);
| ~^ ~~
| | |
| | ll* {aka long long int*}
| int*
| %lld
answer.code:159:25: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
159 | scanf("%d%d",x+i,y+i);
| ~^ ~~~
| | |
| int* ll* {aka long long int*}
| %lld
answer.code:159:27: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
159 | scanf("%d%d",x+i,y+i);
| ~^ ~~~
| | |
| int* ll* {aka long long int*}
| %lld
answer.code:179:18: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘ll’ {aka ‘long long int’} [-Wformat=]
179 | printf("%d\n",SZ(ans));
| ~^
| |
| int
| %lld
answer.code:184: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=]
184 | 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:184: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=]
184 | 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: In function ‘int main()’:
answer.code:189:22: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘ll*’ {aka ‘long long int*’} [-Wformat=]
189 | 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:168:20: required from here
/usr/include/c++/11/bits/predefined_ops.h:69:22: error: no match for ‘operator<’ (operand types are ‘std::pair<long long int, long long int>’ and ‘const std::pair<long long int, int>’)
69 | { return *__it < __val; }
| ~~~~~~^~~~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
from /usr/include/c++/11/algorithm:61,
from answer.code:2:
/usr/include/c++/11/bits/stl_iterator.h:1129:5: note: candidate: ‘...