Submission #769800

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
769800	2023-06-30T09:19:31 Z	akarinkof	Library (JOI18_library)	C++14	100 / 100	503 ms	400 KB

library

#include <cstdio>
#include <vector>
#include "library.h"

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P1;
typedef pair<pair<ll,ll>,ll> P3;
typedef pair<string,ll> Ps;
typedef pair<pair<ll,ll>,pair<ll,ll> > P4;


#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,s,e) for(ll i=s;i<=e;++i)
#define FFOR(i,s,e) for(ll i=s;i>=e;--i)

#define yesno(flg) if(flg){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define ALL(a) (a).begin(),(a).end()
#define mp make_pair
#define pb push_back
#define vl vector<ll>
//#define vs vector<string>
#define so(a) sort(a.begin(),a.end())

#define fi first
#define se second
#define print(a) cout<<a<<endl
#define ssize(a) (ll)(a.size())

#define MAX_N 1002
#define i197 1000000007
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


const ll INF=1000000000000000001;
struct edge
{
	int to, cost;
};

struct pos{
	// 1 変数を入れる;
	ll t;
	ll x,y;
	set<ll> st;

};
int dx[4] = { 1, 0, -1, 0};
int dy[4] = { 0, 1, 0, -1};
int dd[5] = { 0, 1, 0, -1, 0};

vector<vector<int> > vec(1005);
vector<int> c;

void calc(int l,int r,int x,int n){

	vector<int> v1(n);
	//if(x==1)cout<<l<<" "<<r<<endl;
	if(vec[x].size()>=2)return;

	if(l==r){
		if(l==x-1)return;
		if(vec[x].size()==1&&vec[x][0]==l+1)return;

		v1[l]=1;
		v1[x-1]=1;
		if(Query(v1)==1){
			vec[x].pb(l+1);
			vec[l+1].pb(x);
			if(vec[x].size()==2)c.pb(x);
			if(vec[l+1].size()==2)c.pb(l+1);
		}		
		return;
	}
	int mid=(l+r)/2;
	FOR(i,l,mid)v1[i]=1;

	int y=(mid-l+1);

	rep(i,c.size()){
		y-=v1[c[i]-1];
		v1[c[i]-1]=0;
	}
	y-=v1[x-1];
	v1[x-1]=0;



	if(vec[x].size()==1){
		y-=v1[vec[x][0]-1];
		v1[vec[x][0]-1]=0;
		
	}
	if(y==0){
		calc(mid+1,r,x,n);
		return;
	}

	int b=Query(v1);
	v1[x-1]=1;

	int a=Query(v1);

	//cout<<a<<" "<<b<<endl;

	if(b>=a)calc(l,mid,x,n);
	else calc(mid+1,r,x,n);

}

void Solve(int N){
	
	vector<int> ans;
	if(N==1){
		ans.pb(1);
		Answer(ans);
		return;
	}	
	
	queue<int> que;
	que.push(1);

	vector<int> d(N+5);
	while(!que.empty()){
		ll v=que.front();que.pop();
		if(d[v])continue;
		d[v]=1;
		//print(v);

		if(vec[v].size()>=2)continue;
		calc(0,N-1,v,N);
		
		rep(i,vec[v].size()){
			if(d[vec[v][i]]==0)que.push(vec[v][i]);
		}

	}

	que.push(1);

	while(!que.empty()){
		ll v=que.front();que.pop();
		if(v!=1&&d[v])continue;
		d[v]=1;
		
		if(vec[v].size()>=2)continue;

		calc(0,N-1,v,N);
		rep(i,vec[v].size()){
			if(d[vec[v][i]]==0)que.push(vec[v][i]);
		}

	}

	vector<int> f(N+5);
	// FOR(i,1,N){
	// 	rep(j,vec[i].size())cout<<vec[i][j]<<" ";
	// 	cout<<endl;
	// }

	rep(i,N){
		if(vec[i+1].size()==1){
			que.push(i+1);
			break;
		}
	}
	while(!que.empty()){
		ll v=que.front();que.pop();
		if(f[v])continue;
		f[v]=1;
		
		ans.pb(v);
		rep(i,vec[v].size())que.push(vec[v][i]);
	}

	//rep(i,N)print(ans[i]);

	Answer(ans);

}

Compilation message

library.cpp: In function 'void calc(int, int, int, int)':
library.cpp:15:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,n) for(ll i=0;i<n;++i)
......
   84 |  rep(i,c.size()){
      |      ~~~~~~~~~~               
library.cpp:84:2: note: in expansion of macro 'rep'
   84 |  rep(i,c.size()){
      |  ^~~
library.cpp: In function 'void Solve(int)':
library.cpp:15:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,n) for(ll i=0;i<n;++i)
......
  137 |   rep(i,vec[v].size()){
      |       ~~~~~~~~~~~~~~~         
library.cpp:137:3: note: in expansion of macro 'rep'
  137 |   rep(i,vec[v].size()){
      |   ^~~
library.cpp:15:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,n) for(ll i=0;i<n;++i)
......
  153 |   rep(i,vec[v].size()){
      |       ~~~~~~~~~~~~~~~         
library.cpp:153:3: note: in expansion of macro 'rep'
  153 |   rep(i,vec[v].size()){
      |   ^~~
library.cpp:15:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,n) for(ll i=0;i<n;++i)
......
  177 |   rep(i,vec[v].size())que.push(vec[v][i]);
      |       ~~~~~~~~~~~~~~~         
library.cpp:177:3: note: in expansion of macro 'rep'
  177 |   rep(i,vec[v].size())que.push(vec[v][i]);
      |   ^~~

Subtask #1
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	312 KB	# of queries: 2953
2	Correct	26 ms	328 KB	# of queries: 2906
3	Correct	39 ms	336 KB	# of queries: 3091
4	Correct	42 ms	324 KB	# of queries: 3049
5	Correct	45 ms	312 KB	# of queries: 3073
6	Correct	29 ms	316 KB	# of queries: 3097
7	Correct	42 ms	320 KB	# of queries: 3033
8	Correct	43 ms	320 KB	# of queries: 2952
9	Correct	39 ms	308 KB	# of queries: 3092
10	Correct	23 ms	336 KB	# of queries: 1800
11	Correct	1 ms	208 KB	# of queries: 0
12	Correct	0 ms	208 KB	# of queries: 1
13	Correct	0 ms	208 KB	# of queries: 7
14	Correct	1 ms	208 KB	# of queries: 14
15	Correct	2 ms	212 KB	# of queries: 118
16	Correct	3 ms	208 KB	# of queries: 268

Subtask #2
81.0 / 81.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	312 KB	# of queries: 2953
2	Correct	26 ms	328 KB	# of queries: 2906
3	Correct	39 ms	336 KB	# of queries: 3091
4	Correct	42 ms	324 KB	# of queries: 3049
5	Correct	45 ms	312 KB	# of queries: 3073
6	Correct	29 ms	316 KB	# of queries: 3097
7	Correct	42 ms	320 KB	# of queries: 3033
8	Correct	43 ms	320 KB	# of queries: 2952
9	Correct	39 ms	308 KB	# of queries: 3092
10	Correct	23 ms	336 KB	# of queries: 1800
11	Correct	1 ms	208 KB	# of queries: 0
12	Correct	0 ms	208 KB	# of queries: 1
13	Correct	0 ms	208 KB	# of queries: 7
14	Correct	1 ms	208 KB	# of queries: 14
15	Correct	2 ms	212 KB	# of queries: 118
16	Correct	3 ms	208 KB	# of queries: 268
17	Correct	503 ms	380 KB	# of queries: 19753
18	Correct	441 ms	380 KB	# of queries: 19494
19	Correct	442 ms	376 KB	# of queries: 19777
20	Correct	430 ms	380 KB	# of queries: 18591
21	Correct	370 ms	400 KB	# of queries: 17424
22	Correct	430 ms	384 KB	# of queries: 19725
23	Correct	485 ms	384 KB	# of queries: 19764
24	Correct	155 ms	336 KB	# of queries: 9068
25	Correct	438 ms	372 KB	# of queries: 19328
26	Correct	432 ms	384 KB	# of queries: 18054
27	Correct	126 ms	344 KB	# of queries: 9076
28	Correct	327 ms	384 KB	# of queries: 13064
29	Correct	284 ms	380 KB	# of queries: 13055
30	Correct	239 ms	388 KB	# of queries: 13064

Submission #769800

Compilation message

Subtask #1 19.0 / 19.0

Subtask #2 81.0 / 81.0

Subtask #1
19.0 / 19.0

Subtask #2
81.0 / 81.0