Submission #1142532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142532		modwwe	Minerals (JOI19_minerals)	C++20	6 / 100	1 ms	576 KiB

minerals

/// try my best
#include "minerals.h"
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 1e16;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
ll  i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
ll kk;
ll el = 19;/*
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    //modwwe
    phongbeo(),down
    // checktime
}*/
int f[90001];
int color[90001];
int cnt[90001];
bool start[90001];
vector<int> v;
/*
void Answer(int x,int y)
{

    if(color[x]!=color[y])assert(0);
    dem++;
}
int query(int x)
{
    if(start[x])
    {
        cnt[color[x]]--;
        if(cnt[color[x]]==0)dem2--;
    }
    else
    {
        cnt[color[x]]++;
        if(cnt[color[x]]==1)dem2++;
    }
    lim++;
    start[x]=1-start[x];
    return dem2;
}*/
int hihi(int x)
{
    s5=Query(x);
    if(s4!=s5)
    {
        s4=s5;
        return 0;
    }
    return 1;
}
void go(int x,int y)
{
    if(abs(y-r)+abs(x-l)>=r-l+y-x+2)
    {
        for(int i=l; i<=r; i++)
            hihi(f[i]);
        l=x;
        r=y;
        for(int i=l; i<=r; i++)
            hihi(f[i]);
        return;
    }
    while(l<x)
    {
        hihi(f[l]);
        l++;
    }
    while(l>x)
    {
        l--;
        hihi(f[l]);
    }
    while(r<y)
    {
        r++;
        hihi(f[r]);
    }
    while(r>y)
    {
        hihi(f[r]);
        r--;
    }
}
void dnc(vector<int>&a,int x,int y)
{
    if(x>y) return;
    if(a.size()==1)
    {
        Answer(a[0],f[x]);
        return;
    }
    int mid=(x+y)>>1;
    vector<int> left,right;
   // if((x+y)%2==0) mid--;
    go(x,mid);
    for(auto g:a)
    {
        if(left.size()==mid-x+1)
        {
            right.pb(g);
            continue;
        }
        if(right.size()==y-mid)
        {
            left.pb(g);
            continue;
        }
        if(hihi(g))left.pb(g);
        else right.pb(g);
    }
    dnc(left,x,mid);
    dnc(right,mid+1,y);
}
void Solve(int n)
{
    vector<int> a;
    for(int i=1; i<=n*2; i++)
        if(hihi(i))a.pb(i);
        else f[++dem]=i;
    dem=0;
    l=1;
    r=n;
    dnc(a,1,n);
}
void phongbeo()
{
    cin>>n;
    for(int i=1; i<=n*2; i++)
        v.pb(i);
    shuffle(v.begin(),v.end(),rd);
    for(int i=0; i<v.size(); i+=2)
    {
        color[v[i]]=color[v[i+1]]=++dem3;
    }
    Solve(n);
    cout<<dem<<" "<<lim;
}

Compilation message (stderr)

minerals.cpp:39:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   39 | const int inf = 1e16;
      |                 ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10