QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46142#2160. Cardiologydmga44AC ✓64ms3748kbC++172.6kb2022-08-26 05:50:072022-08-26 05:50:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-26 05:50:09]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:3748kb
  • [2022-08-26 05:50:07]
  • 提交

answer

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
// #pragma GCC option("arch=native", "no-zero-upper") // Enable AVX

/// UH Top
#include <bits/stdc++.h>
#define db(x) cerr << #x << ':' << (x) << '\n';
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
#define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)        \
    cout.precision(n); \
    cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi acos(-1)
#define MAXN (ll)(1e6 + 5)

int dist(pii x,vector<pii>& center)
{
    ll ans=1e18;
    for(auto p : center)
        ans=min(ans,abs(p.first-x.first)+abs(p.second-x.second));
    return ans;
}

pii next(int r,int c,int p,int i,int j)
{
    int p1=(p-1)*r+i-1;
    int jp=p1%c+1;
    int ip=p1/c+1;
    return pii(ip,jp);
}

int calc_s(pii ini,int r,int c,int p,pii fin)
{
    int ans=0;
    while(ini!=fin)
    {
        ini=next(r,c,p,ini.first,ini.second);
        ans++;
    }
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll r,c;
    cin >> r >> c;
    int best=1e9;
    pii ij=pii(-1,-1);
    int p,s;
    vector<pii> center;
    for(int i=r/2+(r&1);i<=r/2+1;i++)
        for(int j=c/2+(c&1);j<=c/2+1;j++)
            center.push_back(pii(i,j));
    for(int px=1;px<=c;px++)
    {
        int i,j;
        if(px==1)
        {
            i=1,j=1;
        }
        else if(px==c)
        {
            i=r,j=c;
        }
        else
        {
            ll mul=(px-1)*r;
            if(mul%(c-1)==0)
                continue;
            j=(mul%(c-1))+1;
            i=(mul/(c-1))+1;
        }
        int ss=max(calc_s(pii(1,1),r,c,px,pii(i,j)),calc_s(pii(r,c),r,c,px,pii(i,j)));
        if(dist(pii(i,j),center)<best)
        {
            best=dist(pii(i,j),center);
            ij=pii(i,j);
            p=px;
            s=ss;
        }
    }
    cout << p << ' ' << ij.first << ' ' << ij.second << ' ' << s << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 52ms
memory: 3700kb

input:

6666 966364

output:

473832 3269 483163 2

result:

ok single line: '473832 3269 483163 2'

Test #2:

score: 0
Accepted
time: 43ms
memory: 3656kb

input:

36 906986

output:

12598 1 453493 2

result:

ok single line: '12598 1 453493 2'

Test #3:

score: 0
Accepted
time: 23ms
memory: 3580kb

input:

704877 297616

output:

148803 352426 140980 3

result:

ok single line: '148803 352426 140980 3'

Test #4:

score: 0
Accepted
time: 52ms
memory: 3748kb

input:

1000000 1000000

output:

500000 500000 500000 2

result:

ok single line: '500000 500000 500000 2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

2 2

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1000000 2

output:

1 1 1 21

result:

ok single line: '1 1 1 21'

Test #7:

score: 0
Accepted
time: 44ms
memory: 3524kb

input:

2 1000000

output:

250001 1 500001 2

result:

ok single line: '250001 1 500001 2'

Test #8:

score: 0
Accepted
time: 32ms
memory: 3572kb

input:

985391 511611

output:

255806 492696 255806 3

result:

ok single line: '255806 492696 255806 3'

Test #9:

score: 0
Accepted
time: 35ms
memory: 3656kb

input:

435766 614914

output:

304739 215957 307481 2

result:

ok single line: '304739 215957 307481 2'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

818196 58

output:

29 401921 49 5

result:

ok single line: '29 401921 49 5'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

401765 19

output:

10 200883 10 6

result:

ok single line: '10 200883 10 6'

Test #12:

score: 0
Accepted
time: 44ms
memory: 3572kb

input:

95 912669

output:

456335 48 456335 2

result:

ok single line: '456335 48 456335 2'

Test #13:

score: 0
Accepted
time: 19ms
memory: 3572kb

input:

81 429950

output:

2655 1 214975 2

result:

ok single line: '2655 1 214975 2'

Test #14:

score: 0
Accepted
time: 64ms
memory: 3528kb

input:

999956 999959

output:

249991 249990 499979 3

result:

ok single line: '249991 249990 499979 3'

Test #15:

score: 0
Accepted
time: 61ms
memory: 3736kb

input:

999935 999946

output:

449976 449971 499976 3

result:

ok single line: '449976 449971 499976 3'

Test #16:

score: 0
Accepted
time: 10ms
memory: 3660kb

input:

999951 999952

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #17:

score: 0
Accepted
time: 11ms
memory: 3740kb

input:

106352 224337

output:

112111 53149 112993 2

result:

ok single line: '112111 53149 112993 2'

Test #18:

score: 0
Accepted
time: 48ms
memory: 3748kb

input:

651870 786333

output:

392936 325744 393775 2

result:

ok single line: '392936 325744 393775 2'

Test #19:

score: 0
Accepted
time: 59ms
memory: 3552kb

input:

838522 972888

output:

486249 419093 486853 2

result:

ok single line: '486249 419093 486853 2'