Submission #795835

#	Time	Username	Problem	Language	Result	Execution time	Memory
795835		Antekb	Flights (JOI22_flights)	C++17	68 / 100	229 ms	2204 KiB

Ali

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

namespace {
	vector<int> dep, tab, gdzie;
	vector<vector<int> > E;
	int blo_siz=14;
	int blo_num=1440;
	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;
}
pair<int, int> dec2(int x){
	//cerr<<x<<" ";
	for(int i=0; i<blo_num; i++){
		if(x<blo_num-i){
			//cerr<<i<<" "<<x<<"\n";
			return {i, i+x};
		}
		else x-=blo_num-i;
	}
	assert(false);
}
}
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) {
	pair<int, int> x=dec2(dec(s));
	int b1=x.first, b2=x.second;
	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>
#include<cassert>
#include<iostream>
using namespace std;

namespace {
	int blo_siz=14;
	int blo_num=1440;
	int max_pot=14;
	int X, Y;
string enc(int a){
	string res(20, '0');
	for(int i=0; i<20; i++){
		res[i]='0'+!!(a&(1<<i));
	}
	return res;
}
int dec(string s){
	//cerr<<s<<"\n";
	int res=0;
	for(int i=0; i<s.size(); i++){
		res+=(1<<i)*(s[i]-'0');
	}
	return res;
}
int enc2(int a, int b){
	//cerr<<a<<" "<<b<<" ";
	int r=0;
	for(int i=0; i<a; i++){
		r+=blo_num-i;
	}
	r+=b-a;
	//cerr<<r<<"\n";
	return r;
}
}

string SendB(int N, int _X, int _Y) {
	X=_X;
	Y=_Y;
	if(X>Y)swap(X, Y);
	return enc(enc2(X/blo_siz, 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];
	if(X/blo_siz!=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]);
	}
	}
	else{
		for(int i=X%blo_siz;i<=Y%blo_siz; i++){
			mini=min(mini, blo1[i]);
		}
	}
	return ans-2*mini;
}

Compilation message (stderr)

Ali.cpp: In function 'int {anonymous}::dec(std::string)':
Ali.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~
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: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++){
      |               ~^~~~~~~~~

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