QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#173439#7178. Bishopsucup-team1469#AC ✓496ms95392kbC++1716.6kb2023-09-09 23:36:332023-09-09 23:36:33

Judging History

你现在查看的是最新测评结果

  • [2023-09-09 23:36:33]
  • 评测
  • 测评结果:AC
  • 用时:496ms
  • 内存:95392kb
  • [2023-09-09 23:36:33]
  • 提交

answer

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

using namespace std;
using ll = long long;
using ull = unsigned long long int;
using i128 = __int128_t;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ld = long double;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vc<T>>;
template <typename T> using vvvc = vector<vvc<T>>;
using vi = vc<int>;
using vl = vc<ll>;
using vpi = vc<pii>;
using vpl = vc<pll>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define overload5(a, b, c, d, e, name, ...) name
#define overload4(a, b, c, d, name, ...) name
#define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf)
#define REP1(i, n) for(ll i = 0; i < (n); ++i)
#define REP2(i, a, b) for(ll i = (a); i < (b); ++i)
#define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf)
#define per1(i, n) for(ll i = (n)-1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (a)-1; i >= b; --i)
#define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1, per0)(__VA_ARGS__)
#define fore0(a) rep(a.size())
#define fore1(i, a) for(auto &&i : a)
#define fore2(a, b, v) for(auto &&[a, b] : v)
#define fore3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for(auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define perm(v) for(bool permrepflag = true; (permrepflag ? exchange(permrepflag, false) : next_permutation(all(v)));)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define drop(s) cout << #s << endl, exit(0)
#define si(c) (int)(c).size()
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define lbg(c, x) distance((c).begin(), lower_bound(all(c), (x), greater{}))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define ubg(c, x) distance((c).begin(), upper_bound(all(c), (x), greater{}))
#define rng(v, l, r) v.begin() + (l), v.begin() + (r)
#define all(c) begin(c), end(c)
#define rall(c) rbegin(c), rend(c)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define REV(v) reverse(all(v))
#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())
template <typename T = ll, typename S> T SUM(const S &v) { return accumulate(all(v), T(0)); }
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define INT(...)                                                                                                                                               \
    int __VA_ARGS__;                                                                                                                                           \
    IN(__VA_ARGS__)
#define INTd(...)                                                                                                                                              \
    int __VA_ARGS__;                                                                                                                                           \
    IN2(__VA_ARGS__)
#define LL(...)                                                                                                                                                \
    ll __VA_ARGS__;                                                                                                                                            \
    IN(__VA_ARGS__)
#define LLd(...)                                                                                                                                               \
    ll __VA_ARGS__;                                                                                                                                            \
    IN2(__VA_ARGS__)
#define STR(...)                                                                                                                                               \
    string __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define CHR(...)                                                                                                                                               \
    char __VA_ARGS__;                                                                                                                                          \
    IN(__VA_ARGS__)
#define LD(...)                                                                                                                                               \
    ld __VA_ARGS__;                                                                                                                                        \
    IN(__VA_ARGS__)
#define VEC(type, name, size)                                                                                                                                  \
    vector<type> name(size);                                                                                                                                   \
    IN(name)
#define VECd(type, name, size)                                                                                                                                 \
    vector<type> name(size);                                                                                                                                   \
    IN2(name)
#define VEC2(type, name1, name2, size)                                                                                                                         \
    vector<type> name1(size), name2(size);                                                                                                                     \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i])
#define VEC2d(type, name1, name2, size)                                                                                                                        \
    vector<type> name1(size), name2(size);                                                                                                                     \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)                                                                                                                  \
    vector<type> name1(size), name2(size), name3(size);                                                                                                        \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i])
#define VEC3d(type, name1, name2, name3, size)                                                                                                                 \
    vector<type> name1(size), name2(size), name3(size);                                                                                                        \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)                                                                                                           \
    vector<type> name1(size), name2(size), name3(size), name4(size);                                                                                           \
    for(int i = 0; i < size; i++) IN(name1[i], name2[i], name3[i], name4[i]);
#define VEC4d(type, name1, name2, name3, name4, size)                                                                                                          \
    vector<type> name1(size), name2(size), name3(size), name4(size);                                                                                           \
    for(int i = 0; i < size; i++) IN2(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w)                                                                                                                                   \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN(name)
#define VVd(type, name, h, w)                                                                                                                                  \
    vector<vector<type>> name(h, vector<type>(w));                                                                                                             \
    IN2(name)
int scan() { return getchar(); }
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(ld &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &);
template <class T> void scan(vector<T> &a) {
    for(auto &i : a) scan(i);
}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
void IN2() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
template <class Head, class... Tail> void IN2(Head &head, Tail &...tail) {
    scan(head);
    --head;
    IN2(tail...);
}

template<class T> void prt_(T a){ cout<<a; }
template<class T,class U> void prt_(pair<T,U> a){ cout<<"{"<<a.fi<<", "<<a.se<<"}"; }
void prt_(ld a){ printf("%.15Lf",a); }
template<class T> void prt(vc<T> a){
  for(size_t i=0;i<a.size();++i){
    prt_(a[i]);
    cout<<" \n"[i==a.size()-1];
  }
}
template<class T> void prt(vvc<T> a){
  for(auto& v:a){
    for(size_t i=0;i<v.size();++i){
      prt_(v[i]);
      cout<<" \n"[i==v.size()-1];
    }
  }
}
template<class T> void prt(T a){ prt_(a),cout<<"\n"; }
template<class T,class... Args> void prt(T a,Args... args){ prt_(a),cout<<" ",prt(args...); }

template<class Head,class... Tail> struct multi_dim_vector{ using type=vc<typename multi_dim_vector<Tail...>::type>; };
template<class T> struct multi_dim_vector<T>{ using type=T; };
template<class T,class Arg> vc<T> mvec(int n,Arg&& arg){ return vc<T>(n,arg); }
template<class T,class... Args> class multi_dim_vector<Args...,T>::type mvec(int n,Args&&... args){
  return typename multi_dim_vector<Args...,T>::type(n,mvec<T>(args...));
}

template<class T> T REVed(T a){
  reverse(a.begin(),a.end());
  return a;
}
template<class T> T SORTed(T a){
  sort(a.begin(),a.end());
  return a;
}
template<class T> T RSORTed(T a){
  sort(a.rbegin(),a.rend());
  return a;
}
vi iota(int n){
  vi res(n);
  iota(res.begin(),res.end(),0);
  return res;
}
template <class T> bool chmax(T &a, T b){ return (a < b ? a = b, 1 : 0); }
template <class T> bool chmin(T &a, T b){ return (a > b ? a = b, 1 : 0); }

template<class T> auto runLength(T a) -> vc<pair<typename decltype(a)::value_type,ll>>{
  int n=a.size();
  vc<pair<typename decltype(a)::value_type,ll>> res;
  if(n==0){ return res; }
  typename decltype(a)::value_type now=a[0];
  ll l=1;
  rep(i,1,n){
    if(a[i-1]==a[i]){ l++; }
    else{
      res.pb(now,l);
      now=a[i],l=1;
    }
  }
  res.pb(now,l);
  return res;
}

template<int mod> struct mymodint{
  ll x;
  static constexpr ll get_mod(){ return mod; }
  ll val(){ return x; }
  mymodint(ll x_=0):x((x_%mod+mod)%mod){}
  mymodint operator-(){ return (x==0)?0:mod-x; }
  mymodint operator+(mymodint rhs){ return mymodint(*this)+=rhs; }
  mymodint operator-(mymodint rhs){ return mymodint(*this)-=rhs; }
  mymodint operator*(mymodint rhs){ return mymodint(*this)*=rhs; }
  mymodint operator/(mymodint rhs){ return mymodint(*this)/=rhs; }
  mymodint pow(ll rhs){
    mymodint res=1,now=(*this);
    while(rhs){
      res*=((rhs&1)?now:1),now*=now,rhs>>=1;
    }
    return res;
  }
  mymodint& operator+=(mymodint rhs){
    x+=rhs.x,x-=((x>=mod)?mod:0);
    return (*this);
  }
  mymodint& operator-=(mymodint rhs){
    x-=rhs.x;
    x+=((x<0)?mod:0);
    return (*this);
  }
  mymodint& operator*=(mymodint rhs){
    x=x*rhs.x%mod;
    return (*this);
  }
  mymodint& operator/=(mymodint rhs){ return (*this)*=rhs.pow(mod-2); }
  bool operator==(mymodint rhs){ return x==rhs.x; }
  bool operator!=(mymodint rhs){ return x!=rhs.x; }
};

template<int mod> using modint=
#if __has_include(<atcoder/all>)
  atcoder::static_modint<mod>;
#else
  mymodint<mod>;
#endif

template<int mod> std::ostream& operator<<(std::ostream& os,modint<mod> x){
  return os<<(x.val());
}
template<int mod> std::istream& operator>>(std::istream& is,modint<mod>& x){
  ll t;
  is>>t,x=t;
  return is;
}

template<class T> struct cmb{
  vc<T> fac,ifac;
  cmb(int mx=3000000):fac(mx+1,1),ifac(mx+1,1){
    for(int i=1;i<=mx;++i){ fac[i]=fac[i-1]*i; }
    ifac[mx]/=fac[mx];
    for(int i=mx;i>0;--i){ ifac[i-1]=ifac[i]*i; }
  }
  T operator()(ll n,ll k){
    if(n<0||k<0||n<k){ return 0; }
    return fac[n]*ifac[k]*ifac[n-k];
  }
  T f(ll n){
    return n<0?T(0):fac[n];
  }
  T fi(ll n){
    return n<0?T(0):ifac[n];
  }
};

struct dsu {
  public:
    dsu() : _n(0) {}
    explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

int main(){
  using fp=modint<998244353>;
  INT(n,m);
  if(n==1){
      printf("%d\n",m);
      for(int i=0;i<m;++i){ printf("1 %d\n",i+1); }
      return 0;
  }
  if(m==1){
      printf("%d\n",n);
      for(int i=0;i<n;++i){ printf("%d 1\n",i+1); }
      return 0;
  }
  vvc<pii> G(n+m-1),W(n+m-1);
  for(int j=0;j<=m-1;++j){
      G[m-1-j].pb({0,j});
      W[j].pb({0,j});
      G[n-1+m-1-j].pb({n-1,j});
      W[n-1+j].pb({n-1,j});
  }
  for(int i=1;i<=n-2;++i){
      G[m-1+i].pb({i,0});
      W[i].pb({i,0});
      G[i].pb({i,m-1});
      W[i+m-1].pb({i,m-1});
  }
  map<pii,vc<pii>> jump;
  for(auto v:G){
      if(si(v)!=2){ continue; }
      jump[v[0]].pb(v[1]);
      jump[v[1]].pb(v[0]);
  }
  for(auto v:W){
      if(si(v)!=2){ continue; }
      jump[v[0]].pb(v[1]);
      jump[v[1]].pb(v[0]);
  }
  map<pii,int> seen;
  vpi ans;
  rep(t,4){
      pii v={t%2*(n-1),t/2*(m-1)};
      if(seen[v]){ continue; }
      ans.pb(v);
      seen[v]=1;
      auto c=jump[v][0],prv=v;
      seen[c]=1;
      bool g=0;
      while(c!=v){
          if(g){ ans.pb(c); }
          if(si(jump[c])==1){
              c=jump[c][0];
              seen[c]=1;
              break;
          }
          if(jump[c][0]==prv){ swap(jump[c][0],jump[c][1]); }
          prv=c;
          c=jump[c][0];
          seen[c]=1;
          g^=1;
      }
  }
  for(auto [v,w]:jump){
      if(seen[v]){ continue; }
      ans.pb(v);
      seen[v]=1;
      auto c=jump[v][0],prv=v;
      seen[c]=1;
      bool g=0;
      while(c!=v){
          if(g){ ans.pb(c); }
          if(jump[c][0]==prv){ swap(jump[c][0],jump[c][1]); }
          prv=c;
          c=jump[c][0];
          seen[c]=1;
          g^=1;
      }
  }
  printf("%d\n",si(ans));
  for(auto v:ans){
      printf("%d %d\n",v.fi+1,v.se+1);
  }
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3744kb

input:

2 5

output:

6
1 1
1 3
1 5
2 1
2 3
2 5

result:

ok n: 2, m: 5, bishops: 6

Test #2:

score: 0
Accepted
time: 1ms
memory: 4040kb

input:

5 5

output:

8
1 1
5 1
1 2
5 4
1 3
5 3
1 4
5 2

result:

ok n: 5, m: 5, bishops: 8

Test #3:

score: 0
Accepted
time: 447ms
memory: 95228kb

input:

100000 100000

output:

199998
1 1
100000 1
1 2
100000 99999
1 3
100000 99998
1 4
100000 99997
1 5
100000 99996
1 6
100000 99995
1 7
100000 99994
1 8
100000 99993
1 9
100000 99992
1 10
100000 99991
1 11
100000 99990
1 12
100000 99989
1 13
100000 99988
1 14
100000 99987
1 15
100000 99986
1 16
100000 99985
1 17
100000 99984
...

result:

ok n: 100000, m: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 496ms
memory: 95368kb

input:

100000 99999

output:

199998
1 1
100000 99998
1 3
100000 99996
1 5
100000 99994
1 7
100000 99992
1 9
100000 99990
1 11
100000 99988
1 13
100000 99986
1 15
100000 99984
1 17
100000 99982
1 19
100000 99980
1 21
100000 99978
1 23
100000 99976
1 25
100000 99974
1 27
100000 99972
1 29
100000 99970
1 31
100000 99968
1 33
10000...

result:

ok n: 100000, m: 99999, bishops: 199998

Test #5:

score: 0
Accepted
time: 364ms
memory: 72224kb

input:

100000 50000

output:

149998
1 1
99999 1
50002 50000
1 3
99997 1
50004 50000
1 5
99995 1
50006 50000
1 7
99993 1
50008 50000
1 9
99991 1
50010 50000
1 11
99989 1
50012 50000
1 13
99987 1
50014 50000
1 15
99985 1
50016 50000
1 17
99983 1
50018 50000
1 19
99981 1
50020 50000
1 21
99979 1
50022 50000
1 23
99977 1
50024 5000...

result:

ok n: 100000, m: 50000, bishops: 149998

Test #6:

score: 0
Accepted
time: 5ms
memory: 3848kb

input:

1 100000

output:

100000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 1, m: 100000, bishops: 100000

Test #7:

score: 0
Accepted
time: 441ms
memory: 65680kb

input:

34535 99889

output:

134423
1 1
1 69069
34535 96175
34535 27107
1 7429
1 76497
34535 88747
34535 19679
1 14857
1 83925
34535 81319
34535 12251
1 22285
1 91353
34535 73891
34535 4823
1 29713
1 98781
34535 66463
31929 1
1 37141
6321 99889
34535 59035
24501 1
1 44569
13749 99889
34535 51607
17073 1
1 51997
21177 99889
3453...

result:

ok n: 34535, m: 99889, bishops: 134423

Test #8:

score: 0
Accepted
time: 294ms
memory: 53852kb

input:

12231 97889

output:

110119
1 1
1 24461
1 48921
1 73381
1 97841
12231 85707
12231 61247
12231 36787
12231 12327
97 1
1 24365
1 48825
1 73285
1 97745
12231 85803
12231 61343
12231 36883
12231 12423
193 1
1 24269
1 48729
1 73189
1 97649
12231 85899
12231 61439
12231 36979
12231 12519
289 1
1 24173
1 48633
1 73093
1 97553
...

result:

ok n: 12231, m: 97889, bishops: 110119

Test #9:

score: 0
Accepted
time: 261ms
memory: 53952kb

input:

10000 100000

output:

109998
1 1
1 19999
1 39997
1 59995
1 79993
1 99991
10000 90010
10000 70012
10000 50014
10000 30016
10000 10018
19 1
1 19981
1 39979
1 59977
1 79975
1 99973
10000 90028
10000 70030
10000 50032
10000 30034
10000 10036
37 1
1 19963
1 39961
1 59959
1 79957
1 99955
10000 90046
10000 70048
10000 50050
100...

result:

ok n: 10000, m: 100000, bishops: 109998

Test #10:

score: 0
Accepted
time: 198ms
memory: 49280kb

input:

13 99999

output:

100011
1 1
1 25
1 49
1 73
1 97
1 121
1 145
1 169
1 193
1 217
1 241
1 265
1 289
1 313
1 337
1 361
1 385
1 409
1 433
1 457
1 481
1 505
1 529
1 553
1 577
1 601
1 625
1 649
1 673
1 697
1 721
1 745
1 769
1 793
1 817
1 841
1 865
1 889
1 913
1 937
1 961
1 985
1 1009
1 1033
1 1057
1 1081
1 1105
1 1129
1 115...

result:

ok n: 13, m: 99999, bishops: 100011

Test #11:

score: 0
Accepted
time: 225ms
memory: 49324kb

input:

21 99999

output:

100019
1 1
1 41
1 81
1 121
1 161
1 201
1 241
1 281
1 321
1 361
1 401
1 441
1 481
1 521
1 561
1 601
1 641
1 681
1 721
1 761
1 801
1 841
1 881
1 921
1 961
1 1001
1 1041
1 1081
1 1121
1 1161
1 1201
1 1241
1 1281
1 1321
1 1361
1 1401
1 1441
1 1481
1 1521
1 1561
1 1601
1 1641
1 1681
1 1721
1 1761
1 1801
...

result:

ok n: 21, m: 99999, bishops: 100019

Test #12:

score: 0
Accepted
time: 348ms
memory: 72276kb

input:

49999 100000

output:

149998
1 1
1 99997
49999 50005
7 1
1 99991
49999 50011
13 1
1 99985
49999 50017
19 1
1 99979
49999 50023
25 1
1 99973
49999 50029
31 1
1 99967
49999 50035
37 1
1 99961
49999 50041
43 1
1 99955
49999 50047
49 1
1 99949
49999 50053
55 1
1 99943
49999 50059
61 1
1 99937
49999 50065
67 1
1 99931
49999 5...

result:

ok n: 49999, m: 100000, bishops: 149998

Test #13:

score: 0
Accepted
time: 324ms
memory: 65328kb

input:

33333 99999

output:

133331
1 1
1 66665
33331 99999
33333 33337
5 1
1 66661
33327 99999
33333 33341
9 1
1 66657
33323 99999
33333 33345
13 1
1 66653
33319 99999
33333 33349
17 1
1 66649
33315 99999
33333 33353
21 1
1 66645
33311 99999
33333 33357
25 1
1 66641
33307 99999
33333 33361
29 1
1 66637
33303 99999
33333 33365
...

result:

ok n: 33333, m: 99999, bishops: 133331

Test #14:

score: 0
Accepted
time: 381ms
memory: 59636kb

input:

23342 98876

output:

122216
1 1
1 46683
1 93365
23342 81046
23342 34364
11023 1
1 35661
1 82343
23342 92068
23342 45386
22045 1
1 24639
1 71321
19128 98876
23342 56408
23342 9726
1 13617
1 60299
8106 98876
23342 67430
23342 20748
1 2595
1 49277
1 95959
23342 78452
23342 31770
8429 1
1 38255
1 84937
23342 89474
23342 427...

result:

ok n: 23342, m: 98876, bishops: 122216

Test #15:

score: 0
Accepted
time: 463ms
memory: 71320kb

input:

56713 91234

output:

147946
1 1
22192 91234
56713 12331
1 44383
56713 81373
24661 1
1 88765
56713 36991
1 19723
41914 91234
49321 1
1 64105
56713 61651
4939 1
17254 91234
56713 17269
1 39445
56713 86311
29599 1
1 83827
56713 41929
1 14785
36976 91234
54259 1
1 59167
56713 66589
9877 1
12316 91234
56713 22207
1 34507
566...

result:

ok n: 56713, m: 91234, bishops: 147946

Test #16:

score: 0
Accepted
time: 462ms
memory: 95392kb

input:

99995 99995

output:

199988
1 1
99995 1
1 2
99995 99994
1 3
99995 99993
1 4
99995 99992
1 5
99995 99991
1 6
99995 99990
1 7
99995 99989
1 8
99995 99988
1 9
99995 99987
1 10
99995 99986
1 11
99995 99985
1 12
99995 99984
1 13
99995 99983
1 14
99995 99982
1 15
99995 99981
1 16
99995 99980
1 17
99995 99979
1 18
99995 99978
...

result:

ok n: 99995, m: 99995, bishops: 199988

Test #17:

score: 0
Accepted
time: 153ms
memory: 34368kb

input:

12345 54321

output:

66665
1 1
1 24689
1 49377
12345 46921
12345 22233
9889 1
1 14801
1 39489
9857 54321
12345 32121
12345 7433
1 4913
1 29601
1 54289
12345 42009
12345 17321
4977 1
1 19713
1 44401
12345 51897
12345 27209
12345 2521
1 9825
1 34513
4881 54321
12345 37097
12345 12409
65 1
1 24625
1 49313
12345 46985
12345...

result:

ok n: 12345, m: 54321, bishops: 66665

Test #18:

score: 0
Accepted
time: 486ms
memory: 87116kb

input:

90000 92000

output:

181998
1 1
88000 92000
4001 1
84000 92000
8001 1
80000 92000
12001 1
76000 92000
16001 1
72000 92000
20001 1
68000 92000
24001 1
64000 92000
28001 1
60000 92000
32001 1
56000 92000
36001 1
52000 92000
40001 1
48000 92000
44001 1
44000 92000
48001 1
40000 92000
52001 1
36000 92000
56001 1
32000 92000...

result:

ok n: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 184ms
memory: 40188kb

input:

10000 70000

output:

79998
1 1
1 19999
1 39997
1 59995
9994 70000
10000 50008
10000 30010
10000 10012
13 1
1 19987
1 39985
1 59983
9982 70000
10000 50020
10000 30022
10000 10024
25 1
1 19975
1 39973
1 59971
9970 70000
10000 50032
10000 30034
10000 10036
37 1
1 19963
1 39961
1 59959
9958 70000
10000 50044
10000 30046
100...

result:

ok n: 10000, m: 70000, bishops: 79998

Test #20:

score: 0
Accepted
time: 210ms
memory: 39996kb

input:

10000 70001

output:

80000
1 1
1 19999
1 39997
1 59995
9993 70001
10000 50010
10000 30012
10000 10014
15 1
1 19985
1 39983
1 59981
9979 70001
10000 50024
10000 30026
10000 10028
29 1
1 19971
1 39969
1 59967
9965 70001
10000 50038
10000 30040
10000 10042
43 1
1 19957
1 39955
1 59953
9951 70001
10000 50052
10000 30054
100...

result:

ok n: 10000, m: 70001, bishops: 80000

Test #21:

score: 0
Accepted
time: 229ms
memory: 44804kb

input:

10000 80000

output:

89998
1 1
1 19999
1 39997
1 59995
1 79993
10000 70008
10000 50010
10000 30012
10000 10014
15 1
1 19985
1 39983
1 59981
1 79979
10000 70022
10000 50024
10000 30026
10000 10028
29 1
1 19971
1 39969
1 59967
1 79965
10000 70036
10000 50038
10000 30040
10000 10042
43 1
1 19957
1 39955
1 59953
1 79951
100...

result:

ok n: 10000, m: 80000, bishops: 89998

Test #22:

score: 0
Accepted
time: 226ms
memory: 44656kb

input:

10000 80001

output:

90000
1 1
1 19999
1 39997
1 59995
1 79993
10000 70010
10000 50012
10000 30014
10000 10016
17 1
1 19983
1 39981
1 59979
1 79977
10000 70026
10000 50028
10000 30030
10000 10032
33 1
1 19967
1 39965
1 59963
1 79961
10000 70042
10000 50044
10000 30046
10000 10048
49 1
1 19951
1 39949
1 59947
1 79945
100...

result:

ok n: 10000, m: 80001, bishops: 90000

Test #23:

score: 0
Accepted
time: 199ms
memory: 44852kb

input:

10000 80002

output:

90000
1 1
1 19999
1 39997
1 59995
1 79993
10000 70012
10000 50014
10000 30016
10000 10018
19 1
1 19981
1 39979
1 59977
1 79975
10000 70030
10000 50032
10000 30034
10000 10036
37 1
1 19963
1 39961
1 59959
1 79957
10000 70048
10000 50050
10000 30052
10000 10054
55 1
1 19945
1 39943
1 59941
1 79939
100...

result:

ok n: 10000, m: 80002, bishops: 90000

Test #24:

score: 0
Accepted
time: 214ms
memory: 44712kb

input:

10000 79999

output:

89998
1 1
1 19999
1 39997
1 59995
1 79993
10000 70006
10000 50008
10000 30010
10000 10012
13 1
1 19987
1 39985
1 59983
1 79981
10000 70018
10000 50020
10000 30022
10000 10024
25 1
1 19975
1 39973
1 59971
1 79969
10000 70030
10000 50032
10000 30034
10000 10036
37 1
1 19963
1 39961
1 59959
1 79957
100...

result:

ok n: 10000, m: 79999, bishops: 89998

Test #25:

score: 0
Accepted
time: 222ms
memory: 44792kb

input:

10000 79998

output:

89996
1 1
1 19999
1 39997
1 59995
1 79993
10000 70004
10000 50006
10000 30008
10000 10010
11 1
1 19989
1 39987
1 59985
1 79983
10000 70014
10000 50016
10000 30018
10000 10020
21 1
1 19979
1 39977
1 59975
1 79973
10000 70024
10000 50026
10000 30028
10000 10030
31 1
1 19969
1 39967
1 59965
1 79963
100...

result:

ok n: 10000, m: 79998, bishops: 89996

Test #26:

score: 0
Accepted
time: 284ms
memory: 54772kb

input:

11111 100000

output:

111110
1 1
1 22221
1 44441
1 66661
1 88881
11102 100000
11111 77789
11111 55569
11111 33349
11111 11129
19 1
1 22203
1 44423
1 66643
1 88863
11084 100000
11111 77807
11111 55587
11111 33367
11111 11147
37 1
1 22185
1 44405
1 66625
1 88845
11066 100000
11111 77825
11111 55605
11111 33385
11111 11165
...

result:

ok n: 11111, m: 100000, bishops: 111110

Test #27:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

1 1

output:

1
1 1

result:

ok n: 1, m: 1, bishops: 1

Extra Test:

score: 0
Extra Test Passed