제출 #127599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127599		davitmarg	ICC (CEOI16_icc)	C++17	100 / 100	189 ms	732 KiB

icc

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
 
#ifndef death
 #include "icc.h"
#endif
 
using namespace std;
 
 
#ifdef death
 
int cnt=0;
 
bool query(int n,int m,int* a,int* b)
{
	cnt++;
	//return 0;
    cout<<"?\n";
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
	cout<<endl;
    for(int i=0;i<m;i++)
        cout<<b[i]<<" ";
	cout<<endl;
	int ans;
	cin>>ans;
    return ans;
}
 
void setRoad(int a,int b)
{
	cout<<"! "<<a<<" "<<b<<endl;
}
 
#endif
 
bool query(vector<int> a,vector<int> b)
{
    int A[102],B[102];
    for(int i=0;i<a.size();i++)
        A[i]=a[i];
    for(int i=0;i<b.size();i++)
        B[i]=b[i];
    return query((int)a.size(),(int)b.size(),A,B);
}
 
bool query(vector<vector<int>> A,vector<vector<int>> B)
{
    vector<int> a,b;
    for(int i=0;i<A.size();i++)
        while(!A[i].empty())
		{
            a.PB(A[i].back());
            A[i].pop_back();
		}
 
    for(int i=0;i<B.size();i++)
        while(!B[i].empty())
		{
            b.PB(B[i].back());
            B[i].pop_back();
		}
    if(a.empty() || b.empty())
		return 0;
 
    return query(a,b);
}
 
int n,p[102];
vector<vector<int>> s,t;
vector<int> r;
 
void dsu(int a,int b)
{
    if(s[a].size()<s[b].size())
		swap(a,b);
    vector<int> A,B;
    A=s[a];
	B=s[b];
    while(!s[b].empty())
	{
		p[s[b].back()]=p[s[a][0]];
		s[a].PB(s[b].back());
        s[b].pop_back();
	}
}
 
void get(vector<vector<int>> A,vector<vector<int>> B)
{
    vector<int> a,b;
    int x,y;
    for(int i=0;i<A.size();i++)
        while(!A[i].empty())
		{
            a.PB(A[i].back());
            A[i].pop_back();
		}
 
    for(int i=0;i<B.size();i++)
        while(!B[i].empty())
		{
            b.PB(B[i].back());
            B[i].pop_back();
		}
    random_shuffle(all(a));
    random_shuffle(all(b));
    int l,r,m;
    x=a.back();
    y=b.back();
    l=0;
    r=a.size()-2;
    while(l<=r)
	{
		m=(l+r)/2;
		vector<int> p;
        for(int i=0;i<=m;i++)
			p.PB(a[i]);
        if(query(p,b)==1)
		{
            x=a[m];
			r=m-1;
		}
		else
            l=m+1;
	}
 
 
    l=0;
    r=b.size()-2;
    while(l<=r)
	{
		m=(l+r)/2;
		vector<int> p;
        for(int i=0;i<=m;i++)
			p.PB(b[i]);
        if(query(p,vector<int>(1,x))==1)
		{
            y=b[m];
			r=m-1;
		}
		else
            l=m+1;
	}
 
    setRoad(x,y);
    dsu(p[x],p[y]);
}
 
void solve(int k)
{
    vector<vector<int>> c[2];
    for(int i=1;i<t.size();i++)
        c[(i/k)%2].PB(t[i]);
    if(k==1 || query(c[0],c[1]))
        get(c[0],c[1]);
	else
		return solve(k/2);
}
 
void run(int N)
{
	n=N;
	s.PB(vector<int>(0));
	r.PB(0);
 
    for(int i=1;i<=n;i++)
	{
		s.PB(vector<int>(0));
		r.PB(i);
        s[i].PB(i);
        p[i]=i;
	}
 
    N--;
    N--;
    srand(6848654);
    while(N>0)
	{
		t.resize(1,vector<int>(0));
		for(int i=0;i<s.size();i++)
			if(!s[i].empty())
				t.PB(s[i]);
		int K=0;
		while((1<<K)<(t.size()-1))
			K++;
		K=(1<<K);
		solve(K/2);
	}
 
 
    for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
            if(!s[i].empty() && !s[j].empty())
			{
				get(vector<vector<int>>(1,s[i]),vector<vector<int>>(1,s[j]));
                break;
			}
}
 
 
#ifdef death
 
int main()
{
	int N;
	cin>>N;
    run(N);
    cout<<"!! "<<cnt<<" !!"<<endl;
	return 0;
}
 
#endif
 
 
/*
 
 
 
 
*/

컴파일 시 표준 에러 (stderr) 메시지

icc.cpp: In function 'bool query(std::vector<int>, std::vector<int>)':
icc.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)
                 ~^~~~~~~~~
icc.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<b.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'bool query(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
icc.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<B.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void get(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:113:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
icc.cpp:120:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<B.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void solve(int)':
icc.cpp:173:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<t.size();i++)
                 ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:201:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();i++)
               ~^~~~~~~~~
icc.cpp:205:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while((1<<K)<(t.size()-1))
         ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10