Submission #1149491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149491		modwwe	Chameleon's Love (JOI20_chameleon)	C++20	4 / 100	18 ms	532 KiB

chameleon

//#include "gap.h"
#include "chameleon.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#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 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());
int rand(int l,int r)
{
    return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e16;
const ll mod2 = 1e9+7;
const ll base=67;
int  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;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int t;
int el = 19;/*
main()
{
    if(fopen(task2".inp","r"))
    {
        fin(task2);
        fou(task2);
    }
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    /// cin>>s1;
//int t;cin>>t; while(t--)
    phongbeo();
    // checktime
}
const int Q_MAX = 20'000;
const int N_MAX = 500;

int N;
int Y[N_MAX * 2 + 1], C[N_MAX * 2 + 1], L[N_MAX * 2 + 1];

int query_count = 0;
int answer_count = 0;
bool finishes[N_MAX * 2 + 1];

void WrongAnswer(int code)
{
    printf("Wrong Answer [%d]\n", code);
    exit(0);
}*/
vector<int> v[1001];
bool vis[1001];
vector<int> ke[1001];
bool use[1001];
void dfs(int x,int y)
{
    vis[x]=1;
    v[y].pb(x);
    for(auto f:ke[x])
        if(!vis[f])
            dfs(f,1-y);
}/*
int Query(const std::vector<int> &p)
{
    if (++query_count > Q_MAX) WrongAnswer(3);
    bool presents[N_MAX * 2 + 1];
    for (int i = 1; i <= N * 2; ++i) presents[i] = false;
    for (const int k : p)
    {
        if (k <= 0 || k > N * 2) WrongAnswer(1);
        if (presents[k]) WrongAnswer(2);
        presents[k] = true;
    }
    bool colors[N_MAX + 1];
    for (int j = 1; j <= N; ++j) colors[j] = false;
    int color_count = 0;
    for (int i = 1; i <= N * 2; ++i)
    {
        if (!presents[i]) continue;
        const int color = presents[L[i]] ? C[L[i]] : C[i];
        if (!colors[color])
        {
            ++color_count;
            colors[color] = true;
        }
    }
    return color_count;
}

void Answer(int a, int b)
{
    ++answer_count;
    if (a <= 0 || a > N * 2) WrongAnswer(4);
    if (b <= 0 || b > N * 2) WrongAnswer(4);
    if (finishes[a]) WrongAnswer(5);
    finishes[a] = true;
    if (finishes[b]) WrongAnswer(5);
    finishes[b] = true;
    if (C[a] != C[b]) WrongAnswer(6);
}*/
bool check(int x,int y)
{
    vector<int> hihi;
    for(int i=1; i<=2*n; i++)
        if(i!=x&&i!=y)
            hihi.pb(i);
    return (Query(hihi)!=n);
}
void Solve(int N)
{
    n=N;
///lx=i or li=x  or ci=cx
    for(int i=2; i<=2*n; i++)
    {
        memset(vis,0,sizeof vis);
        for(int j=1; j<i; j++)
            if(!vis[j])dfs(j,0);
        for(int j=0; j<2; j++)
        {
            while(true)
            {
                v[j].pb(i);
                if(Query(v[j])==v[j].size()) break;
                v[j].pop_back();
                l=1;
                r=v[j].size()-1;
                while(l<=r)
                {
                    int mid=l+r>>1;
                    vector<int>haha;
                    for(int f=mid; f<v[j].size(); f++)
                        haha.pb(v[j][f]);
                    haha.pb(i);
                    if(Query(haha)==haha.size())r=mid-1;
                    else l=mid+1;
                }
                s2=v[j][r];
                ke[s2].pb(i);
                ke[i].pb(s2);
                reverse(v[j].begin(),v[j].end());
                while(true)
                {
                    if(v[j].back()==s2)
                    {
                        v[j].pop_back();
                        break;
                    }
                    v[j].pop_back();
                }
            }
            v[j].clear();
        }
    }
    for(int i=1; i<=n*2; i++)
        for(auto x:ke[i])
            if(x>i&&!use[x])
                if(check(x,i))
                        Answer(x,i),use[x]=1;
}
/*
void phongbeo()
{
    if (scanf("%d", &N) != 1)
    {
        fprintf(stderr, "Error while reading input.\n");
        exit(1);
    }
    for (int i = 1; i <= N * 2; ++i)
    {
        if (scanf("%d", &Y[i]) != 1)
        {
            fprintf(stderr, "Error while reading input.\n");
            exit(1);
        }
    }
    for (int i = 1; i <= N * 2; ++i)
    {
        if (scanf("%d", &C[i]) != 1)
        {
            fprintf(stderr, "Error while reading input.\n");
            exit(1);
        }
    }
    for (int i = 1; i <= N * 2; ++i)
    {
        if (scanf("%d", &L[i]) != 1)
        {
            fprintf(stderr, "Error while reading input.\n");
            exit(1);
        }
    }
    for (int i = 1; i <= N * 2; ++i) finishes[i] = false;
    Solve(N);
    if (answer_count != N) WrongAnswer(7);
    printf("Accepted: %d\n", query_count);
}
*/

Compilation message (stderr)

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

• Subtask 1: 4 / 4
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36