oj.uz

Submission #213498

# Submission time Handle Problem Language Result Execution time Memory
213498 2020-03-26T02:19:07 Z username Chameleon's Love (JOI20_chameleon) C++14
20 / 100
 54 ms 4480 KB 
#include "chameleon.h"
//
#include<bits/stdc++.h>
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb push_back
using namespace std;

namespace ch{
	bool check(int x,int l,int r){
		vector<int>tt;
		tt.pb(x+1);
		REP(i,l,r)tt.pb(i+1);
		return Query(tt)<r-l+1;
	}
	vector<int>dfs(int x,int l,int r){
		vector<int>re,tt;
		if(l+1==r)re.pb(l);
		else{
			int mid=l+r>>1;
			if(check(x,l,mid)){
				tt=dfs(x,l,mid);
				re.insert(re.end(),tt.begin(),tt.end());
			}
			if(check(x,mid,r)){
				tt=dfs(x,mid,r);
				re.insert(re.end(),tt.begin(),tt.end());
			}
		}
		return re;
	}
}

void Solve(int n){
	const int maxm=1009;
	vector<int>g[maxm];
	int m,mch[maxm],eds[maxm][maxm];
	m=n<<1;
	REP(i,0,n){
		int l=n,r=m;
		while(1){
			if(!ch::check(i,l,r))break;
			while(l+1<r){
				int mid=l+r>>1;
				if(ch::check(i,l,mid))r=mid;
				else l=mid;
			}
			g[i].pb(l);
			g[l].pb(i);
			eds[i][l]=eds[l][i]=1;
			l=r,r=m;
		}
	}
	REP(u,0,m){
		if(g[u].size()<2)continue;
		REP(i,1,g[u].size()){
			int v=g[u][i];
			vector<int>tt;
			tt.pb(u+1);
			REP(j,0,g[u].size()){
				if(j!=i){
					tt.pb(g[u][j]+1);
				}
			}
			if(Query(tt)==1){
				eds[u][v]=eds[v][u]=0;
				goto fin;
			}
		}
		eds[u][g[u][0]]=eds[g[u][0]][u]=0;
		fin:;
	}
	REP(i,0,n){
		REP(j,0,g[i].size()){
			int v=g[i][j];
			if(eds[i][v]){
				mch[i]=v;
			}
		}
	}
	REP(i,0,n)Answer(i+1,mch[i]+1);
}
//

Compilation message

chameleon.cpp: In function 'std::vector<int> ch::dfs(int, int, int)':
chameleon.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=l+r>>1;
            ~^~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:55:3: note: in expansion of macro 'REP'
   REP(i,1,g[u].size()){
   ^~~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:59:4: note: in expansion of macro 'REP'
    REP(j,0,g[u].size()){
    ^~~
chameleon.cpp:4:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
chameleon.cpp:73:3: note: in expansion of macro 'REP'
   REP(j,0,g[i].size()){
   ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 54 ms 1912 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 45 ms 4344 KB Output is correct
4 Correct 46 ms 4480 KB Output is correct
5 Correct 47 ms 4476 KB Output is correct
6 Correct 45 ms 4344 KB Output is correct
7 Correct 45 ms 4344 KB Output is correct
8 Correct 46 ms 4344 KB Output is correct
9 Correct 48 ms 4344 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Incorrect 54 ms 1912 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -