Submission #795768

#	Time	Username	Problem	Language	Result	Execution time	Memory
795768		Antekb	Flights (JOI22_flights)	C++17	15 / 100	6 ms	2136 KiB

Ali

#include "Ali.h"
#include <string>
#include <vector>
#include<iostream>
#define pb push_back
using namespace std;

namespace {
	vector<int> dep, tab, gdzie;
	vector<vector<int> > E;
	int blo_siz=30;
	int blo_num=(1<<10);
	int max_pot=14;
string enc(int a){
	string res(max_pot, '0');
	for(int i=0; i<max_pot; i++){
		res[i]='0'+!!(a&(1<<i));
	}
	return res;
}
int dec(string s){
	int res=0;
	for(int i=0; i<s.size(); i++){
		res+=(1<<i)*(s[i]-'0');
	}
	return res;
}
}
void dfs(int v, int p){
	//cerr<<v<<" "<<p<<endl;
	gdzie[v]=tab.size();
	tab.pb(dep[v]);
	for(int u:E[v]){
		if(u!=p){
			dep[u]=dep[v]+1;
			dfs(u, v);
			tab.pb(dep[v]);
		}
	}
}
void Init(int n, std::vector<int> U, std::vector<int> V) {
	E.clear();
	gdzie.clear();
	dep.clear();
	tab.clear();
	gdzie.resize(n);
	dep.resize(n);
	E.resize(n);
	for(int i=0; i<n-1; i++){
		//cerr<<U[i]<<" "<<V[i]<<endl;
		E[U[i]].pb(V[i]);
		E[V[i]].pb(U[i]);
	}
	dfs(0, -1);
	for(int i=0; i<n; i++){
		SetID(i, gdzie[i]);
	}
	while(tab.size()%blo_siz){
		tab.pb(tab.back()+1);
	}
}

string SendA(std::string s) {
	int b1=dec(s.substr(0, 10)), b2=dec(s.substr(10, 10));
	int mini=(1<<max_pot)-1;
	string res;
	for(int i=b1+1; i<b2; i++){
		for(int j=i*blo_siz; j<(i+1)*blo_siz; j++){
			mini=min(mini, tab[j]);
		}
	}
	res+=enc(mini);
	res+=enc(tab[b1*blo_siz]);
	for(int i=b1*blo_siz+1; i<blo_siz*(b1+1); i++){
		res+='0'+char(tab[i]>tab[i-1]);
	}
	res+=enc(tab[b2*blo_siz]);
	for(int i=b2*blo_siz+1; i<blo_siz*(b2+1); i++){
		res+='0'+char(tab[i]>tab[i-1]);
	}
	return res;
}

Benjamin

#include "Benjamin.h"
#include <string>
#include <vector>
using namespace std;

namespace {
	int blo_siz=30;
	int blo_num=(1<<10);
	int max_pot=14;
	int X, Y;
string enc(int a){
	string res(10, '0');
	for(int i=0; i<10; i++){
		res[i]='0'+!!(a&(1<<i));
	}
	return res;
}
int dec(string s){
	int res=0;
	for(int i=0; i<s.size(); i++){
		res+=(1<<i)*(s[i]-'0');
	}
	return res;
}
}

string SendB(int N, int _X, int _Y) {
	X=_X;
	Y=_Y;
	if(X>Y)swap(X, Y);
	return enc(X/blo_siz)+enc(Y/blo_siz);
}

int Answer(string s) {
	int mini=dec(s.substr(0, max_pot));
	vector<int> blo1(blo_siz), blo2(blo_siz);
	blo1[0]=dec(s.substr(max_pot, max_pot));
	for(int i=1; i<blo_siz;i++){
		if(s[max_pot*2-1+i]=='1')blo1[i]=blo1[i-1]+1;
		else blo1[i]=blo1[i-1]-1;
	}
	blo2[0]=dec(s.substr(2*max_pot+blo_siz-1, max_pot));
	for(int i=1; i<blo_siz;i++){
		if(s[max_pot*3+blo_siz-2+i]=='1')blo2[i]=blo2[i-1]+1;
		else blo2[i]=blo2[i-1]-1;
	}
	int ans=blo1[X%blo_siz]+blo2[Y%blo_siz];
	for(int i=X%blo_siz;i<blo_siz; i++){
		mini=min(mini, blo1[i]);
	}
	for(int i=Y%blo_siz;i>=0; i--){
		mini=min(mini, blo2[i]);
	}
	return ans-2*mini;
}

Compilation message (stderr)

Ali.cpp: In function 'int {anonymous}::dec(std::string)':
Ali.cpp:23:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~
Ali.cpp: At global scope:
Ali.cpp:12:6: warning: '{anonymous}::blo_num' defined but not used [-Wunused-variable]
   12 |  int blo_num=(1<<10);
      |      ^~~~~~~
grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'int {anonymous}::dec(std::string)':
Benjamin.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~
Benjamin.cpp: At global scope:
Benjamin.cpp:8:6: warning: '{anonymous}::blo_num' defined but not used [-Wunused-variable]
    8 |  int blo_num=(1<<10);
      |      ^~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85