oj.uz

Submission #830089

# Submission time Handle Problem Language Result Execution time Memory
830089 2023-08-18T18:39:13 Z Antekb Saveit (IOI10_saveit) C++17
0 / 100
 1846 ms 12872 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
using vii = vector<pii>;
void nadaj(vi &V, int x, int b){
	for(int i=0; i<b; i++){
		V.pb(!!(x&(1<<i)));
	}
}
void encode2(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	bool spec[n];
	queue<int> spe;
	for(int v=0; v<n; v++){
		int ile=0;
		vii V2;
		for(int u=0; u<n; u++){
			if(u==v)continue;
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			b=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					V2.eb(u, i);
					b=1;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					V2.eb(v, i);
					b=1;
				}
			}
			if(b)ile++;
		}
		sort(all(V2));
		V2.resize(unique(all(V2))-V2.begin());
		spec[v]=(ile>=111);
		if(ile>=111){
			spe.push(v);
			for(int u=0; u<n; u++){
				if(u==v)continue;
				bool b=1;
				for(int i=0; i<h; i++){
					if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
						b=0;
					}
				}
				if(!b)continue;
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
						E2[v].pb(u);
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
						E2[v].pb(u);
					}
				}
			}
		}
	}
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<=n)E2[v].pb(u);
				else E2[u].pb(v);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	while(spe.size()){
		int v=spe.front();
		spe.pop();
		if(E2[v].size()>=111)continue;
		vi V;
		spec[v]=0;
		for(int u:E2[v]){
			if(2*(u-v)<=n)V.pb(u);
			else{
				E2[u].pb(v);
				if(E2[u].size()==111){
					spec[u]=1;
					spe.push(u);
				}
			}
		}
		E2[v]=V;
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		if(spec[i]){
			nadaj(ans, 111, 7);
		}
		else{
			assert(E2[i].size()<100);
			nadaj(ans, E2[i].size(), 7);
		}
		//assert(spec[i]==(E2[i].size()>=111));
		if(spec[i]){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, (u-i+n)%n, 9);
			}
		}
	}
	return;
}
void encode3(vi &ans, int n, int h, int m, int *v1, int *v2){
	vi E[n];
	int czy[n][h], dist[n][h];
	for(int i=0; i<n; i++){
		for(int j=0; j<h; j++){
			czy[i][j]=(i==j);
			dist[i][j]=1e9*(i!=j);
		}
	}
	vi edg;
	for(int i=0; i<m; i++){
		E[v1[i]].pb(edg.size());
		edg.pb(v2[i]);
		E[v2[i]].pb(edg.size());
		edg.pb(v1[i]);
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int e:E[v]){
				if(dist[edg[e]][s]==1e9){
					dist[edg[e]][s]=dist[v][s]+1;
					V.pb(edg[e]);
				}
			}
		}
	}
	vi E2[n];
	int sum=0;
	for(int t=h; t>0; t--){
		for(int u=0; u<n; u++){
			for(int v=0; v<u; v++){
			bool b=1;
			for(int i=0; i<h; i++){
				if(dist[u][i]+1<dist[v][i] || dist[v][i]+1<dist[u][i]){
					b=0;
				}
			}
			if(!b)continue;
			int ile=0;
			for(int i=0; i<h; i++){
				if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
					ile++;
				}
				if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
					ile++;
				}
			}
			if(ile==t){
				//cerr<<t<<"\n";
				sum+=t;
				if(2*(u-v)<=n)E2[v].pb(u);
				else E2[u].pb(v);
				for(int i=0; i<h; i++){
					if(!czy[u][i] && dist[u][i]==dist[v][i]+1){
						czy[u][i]=1;
					}
					if(!czy[v][i] && dist[v][i]==dist[u][i]+1){
						czy[v][i]=1;
					}
				}
			}
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		nadaj(ans, min((int)E2[i].size(), 111), 7);
		if(E2[i].size()>=111){
			vi V(n);
			for(int u:E2[i]){
				V[u]=1;
			}
			for(int j:V){
				nadaj(ans, j, 1);
			}
		}
		else{
			for(int u:E2[i]){
				nadaj(ans, (u-i+n)%n, 9);
			}
		}
	}
	return;
}
void encode(int n, int h, int m, int *v1, int *v2){
	vi V, V2;
	encode2(V, n, h, m, v1, v2);
	//encode3(V2, n, h, m, v1, v2);
	//if(V2.size()<V.size())V=V2;
	for(int i:V){
		encode_bit(i);
	}
}
#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pp pop_back;
using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;
int czytaj(int b){
	int x=0;
	for(int i=0; i<b; i++){
		x+=(int(decode_bit())<<i);
	}
	return x;
}
void decode(int n, int h) {
	vi E[n];
	for(int i=0;i<n; i++){
		int k=czytaj(7);
		//cerr<<k<<"\n";
		if(k>=111){
			for(int j=0; j<n; j++){
				if(czytaj(1)){
					E[i].pb(j);
					E[j].pb(i);
				}
			}
		}
		else{
			while(k--){
				int j=czytaj(9);
				E[i].pb((j+i)%n);
				E[(j+i)%n].pb(i);
			}
		}
	}
	for(int s=0; s<h; s++){
		vi V;
		V.pb(s);
		vi dist(n, 1e9);
		dist[s]=0;
		for(int i=0; i<V.size(); i++){
			int v=V[i];
			for(int u:E[v]){
				if(dist[u]==1e9){
					dist[u]=dist[v]+1;
					V.pb(u);
				}
			}
		}
		for(int i=0; i<n; i++){
			hops(s, i, dist[i]);
		}
	}
}

Compilation message

encoder.cpp: In function 'void encode2(vi&, int, int, int, int*, int*)':
encoder.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:206:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0; i<V.size(); i++){
      |                ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 12872 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 802 ms 5800 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 982 ms 6752 KB Output isn't correct
6 Incorrect 1194 ms 6964 KB Output isn't correct
7 Incorrect 1678 ms 7200 KB Output isn't correct
8 Correct 1222 ms 5408 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 818 ms 5400 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 836 ms 5500 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 936 ms 6012 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 953 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1759 ms 7124 KB Output isn't correct
14 Correct 953 ms 5436 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 960 ms 5584 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1071 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1069 ms 6436 KB Output isn't correct
18 Incorrect 1202 ms 6996 KB Output isn't correct
19 Incorrect 1347 ms 6548 KB Output isn't correct
20 Correct 1268 ms 7444 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1351 ms 7776 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1846 ms 7120 KB Output isn't correct
23 Correct 1427 ms 7964 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 12872 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 802 ms 5800 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 982 ms 6752 KB Output isn't correct
6 Incorrect 1194 ms 6964 KB Output isn't correct
7 Incorrect 1678 ms 7200 KB Output isn't correct
8 Correct 1222 ms 5408 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 818 ms 5400 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 836 ms 5500 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 936 ms 6012 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 953 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1759 ms 7124 KB Output isn't correct
14 Correct 953 ms 5436 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 960 ms 5584 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1071 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1069 ms 6436 KB Output isn't correct
18 Incorrect 1202 ms 6996 KB Output isn't correct
19 Incorrect 1347 ms 6548 KB Output isn't correct
20 Correct 1268 ms 7444 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1351 ms 7776 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1846 ms 7120 KB Output isn't correct
23 Correct 1427 ms 7964 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 12872 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 802 ms 5800 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 982 ms 6752 KB Output isn't correct
6 Incorrect 1194 ms 6964 KB Output isn't correct
7 Incorrect 1678 ms 7200 KB Output isn't correct
8 Correct 1222 ms 5408 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 818 ms 5400 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 836 ms 5500 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 936 ms 6012 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 953 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1759 ms 7124 KB Output isn't correct
14 Correct 953 ms 5436 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 960 ms 5584 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1071 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1069 ms 6436 KB Output isn't correct
18 Incorrect 1202 ms 6996 KB Output isn't correct
19 Incorrect 1347 ms 6548 KB Output isn't correct
20 Correct 1268 ms 7444 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1351 ms 7776 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1846 ms 7120 KB Output isn't correct
23 Correct 1427 ms 7964 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1668 ms 12872 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 2 ms 4604 KB Output is correct - 98 call(s) of encode_bit()
3 Correct 802 ms 5800 KB Output is correct - 40689 call(s) of encode_bit()
4 Correct 3 ms 4612 KB Output is correct - 116 call(s) of encode_bit()
5 Incorrect 982 ms 6752 KB Output isn't correct
6 Incorrect 1194 ms 6964 KB Output isn't correct
7 Incorrect 1678 ms 7200 KB Output isn't correct
8 Correct 1222 ms 5408 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 818 ms 5400 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 836 ms 5500 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 936 ms 6012 KB Output is correct - 37973 call(s) of encode_bit()
12 Correct 953 ms 5268 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 1759 ms 7124 KB Output isn't correct
14 Correct 953 ms 5436 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 960 ms 5584 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 1071 ms 6464 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 1069 ms 6436 KB Output isn't correct
18 Incorrect 1202 ms 6996 KB Output isn't correct
19 Incorrect 1347 ms 6548 KB Output isn't correct
20 Correct 1268 ms 7444 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 1351 ms 7776 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 1846 ms 7120 KB Output isn't correct
23 Correct 1427 ms 7964 KB Output is correct - 60188 call(s) of encode_bit()