Submission #3911732


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<llll> vllll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define repC3(vari,varj,vark,n)  for(int vari=0;vari<(n)-2;++vari)for(int varj=vari+1;varj<(n)-1;++varj)for(int vark=varj+1;vark<(n);++vark)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }
template<typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template<typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];


ll solve(int N, vi& a, vi& b) {
    vll fact(N+1);
    fact[0] = 0; fact[1] = 1;
    for(int i=2; i<=N; ++i) fact[i] = MUL(i, fact[i-1]);

    sort(ALL(a)); sort(ALL(b));
    vector<ii> c(N);
    rep(i,N){
        c[i] = ii( min(a[i],b[i]), max(a[i],b[i]) );
    }
    sort(ALL(c));

    vi till(N);
    deque<int> dq;
    dq.push_back(0);

    rep1(i,N-1) {
        while (!dq.empty() && c[dq.front()].second < c[i].first) {
            till[dq.front()] = i-1;
            dq.pop_front();
        }
        dq.push_back(i);
    }
    while (!dq.empty()) {
        till[dq.front()] = N-1;
        dq.pop_front();
    }
    rep(i,N) till[i] -= i-1;
    ll ans = till[0];
    rep1(i,N-1) ans = MUL(ans, till[i]);

    return ans;
}


int main() {
    int N; scanf("%d", &N);
    vi a(N), b(N);
    rep(i,N){
        scanf("%d", &a[i]);
    }
    rep(i,N){
        scanf("%d", &b[i]);
    }
    cout << solve(N,a,b) << endl;
    return 0;
}

Submission Info

Submission Time
Task A - 1D Matching
User naoya_t
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3271 Byte
Status
Exec Time 42 ms
Memory 3456 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:100:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     int N; scanf("%d", &N);
                           ^
./Main.cpp:103:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
                           ^
./Main.cpp:106:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
                           ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 26 ms 1920 KB
001.txt 10 ms 896 KB
002.txt 13 ms 1024 KB
003.txt 15 ms 1152 KB
004.txt 38 ms 2688 KB
005.txt 42 ms 2944 KB
006.txt 42 ms 2944 KB
007.txt 42 ms 2944 KB
008.txt 42 ms 2944 KB
009.txt 42 ms 2944 KB
010.txt 41 ms 3456 KB
011.txt 41 ms 2944 KB
example0.txt 1 ms 256 KB
example1.txt 1 ms 256 KB