oj.uz

Submission #830121

# Submission time Handle Problem Language Result Execution time Memory
830121 2023-08-18T19:06:37 Z Antekb Saveit (IOI10_saveit) C++17
100 / 100
 6372 ms 13808 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());
		if(ile>=111){
			spe.push(v);
			spec[v]=1;
			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;
					}
				}
			}
			}
		}
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				assert(((u-i+n)%n)<512);
			}
		}
	}
	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)%n)<=n)V.pb(u);
			else{
				E2[u].pb(v);
				if(E2[u].size()==111){
					spec[u]=1;
					spe.push(u);
				}
				if(!spec[u]){
					for(int i:E2[u]){
						assert(((i-u+n)%n)<512);
					}
				}
			}
		}
		E2[v]=V;
		for(int u:E2[v]){
			assert(((u-v+n)%n)<512);
		}
	}
	for(int i=0; i<n; i++){
		if(!spec[i]){
			for(int u:E2[i]){
				//assert(((u-i+n)%n)<512);
			}
		}
	}
	cerr<<sum<<"\n";
	for(int i=0; i<n; i++){
		sort(E2[i].begin(), E2[i].end());
		if(spec[i]){
			//assert(E2[i].size()>=111);
			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]){
				//assert((u-i+n)%n<512);
				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:176:12: warning: unused variable 'u' [-Wunused-variable]
  176 |    for(int u:E2[i]){
      |            ^
encoder.cpp: In function 'void encode3(vi&, int, int, int, int*, int*)':
encoder.cpp:230:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |   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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6372 ms 13808 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 1655 ms 5900 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 73 call(s) of encode_bit()
5 Correct 2729 ms 6824 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3375 ms 6888 KB Output is correct - 69064 call(s) of encode_bit()
7 Correct 4162 ms 7520 KB Output is correct - 67397 call(s) of encode_bit()
8 Correct 2936 ms 5540 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1591 ms 5612 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1611 ms 5568 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1799 ms 6256 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1910 ms 5520 KB Output is correct - 15991 call(s) of encode_bit()
13 Correct 3546 ms 7344 KB Output is correct - 48208 call(s) of encode_bit()
14 Correct 2028 ms 5652 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1986 ms 5724 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2364 ms 6816 KB Output is correct - 33199 call(s) of encode_bit()
17 Correct 2423 ms 6760 KB Output is correct - 32992 call(s) of encode_bit()
18 Correct 3288 ms 7508 KB Output is correct - 47289 call(s) of encode_bit()
19 Correct 2856 ms 6744 KB Output is correct - 46802 call(s) of encode_bit()
20 Correct 3350 ms 7864 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3887 ms 8352 KB Output is correct - 52427 call(s) of encode_bit()
22 Correct 3735 ms 7816 KB Output is correct - 56170 call(s) of encode_bit()
23 Correct 3935 ms 9088 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6372 ms 13808 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 1655 ms 5900 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 73 call(s) of encode_bit()
5 Correct 2729 ms 6824 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3375 ms 6888 KB Output is correct - 69064 call(s) of encode_bit()
7 Correct 4162 ms 7520 KB Output is correct - 67397 call(s) of encode_bit()
8 Correct 2936 ms 5540 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1591 ms 5612 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1611 ms 5568 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1799 ms 6256 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1910 ms 5520 KB Output is correct - 15991 call(s) of encode_bit()
13 Correct 3546 ms 7344 KB Output is correct - 48208 call(s) of encode_bit()
14 Correct 2028 ms 5652 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1986 ms 5724 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2364 ms 6816 KB Output is correct - 33199 call(s) of encode_bit()
17 Correct 2423 ms 6760 KB Output is correct - 32992 call(s) of encode_bit()
18 Correct 3288 ms 7508 KB Output is correct - 47289 call(s) of encode_bit()
19 Correct 2856 ms 6744 KB Output is correct - 46802 call(s) of encode_bit()
20 Correct 3350 ms 7864 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3887 ms 8352 KB Output is correct - 52427 call(s) of encode_bit()
22 Correct 3735 ms 7816 KB Output is correct - 56170 call(s) of encode_bit()
23 Correct 3935 ms 9088 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6372 ms 13808 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 1655 ms 5900 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 73 call(s) of encode_bit()
5 Correct 2729 ms 6824 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3375 ms 6888 KB Output is correct - 69064 call(s) of encode_bit()
7 Correct 4162 ms 7520 KB Output is correct - 67397 call(s) of encode_bit()
8 Correct 2936 ms 5540 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1591 ms 5612 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1611 ms 5568 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1799 ms 6256 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1910 ms 5520 KB Output is correct - 15991 call(s) of encode_bit()
13 Correct 3546 ms 7344 KB Output is correct - 48208 call(s) of encode_bit()
14 Correct 2028 ms 5652 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1986 ms 5724 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2364 ms 6816 KB Output is correct - 33199 call(s) of encode_bit()
17 Correct 2423 ms 6760 KB Output is correct - 32992 call(s) of encode_bit()
18 Correct 3288 ms 7508 KB Output is correct - 47289 call(s) of encode_bit()
19 Correct 2856 ms 6744 KB Output is correct - 46802 call(s) of encode_bit()
20 Correct 3350 ms 7864 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3887 ms 8352 KB Output is correct - 52427 call(s) of encode_bit()
22 Correct 3735 ms 7816 KB Output is correct - 56170 call(s) of encode_bit()
23 Correct 3935 ms 9088 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6372 ms 13808 KB Output is correct - 43000 call(s) of encode_bit()
2 Correct 1 ms 4616 KB Output is correct - 73 call(s) of encode_bit()
3 Correct 1655 ms 5900 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 2 ms 4608 KB Output is correct - 73 call(s) of encode_bit()
5 Correct 2729 ms 6824 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3375 ms 6888 KB Output is correct - 69064 call(s) of encode_bit()
7 Correct 4162 ms 7520 KB Output is correct - 67397 call(s) of encode_bit()
8 Correct 2936 ms 5540 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1591 ms 5612 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1611 ms 5568 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1799 ms 6256 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1910 ms 5520 KB Output is correct - 15991 call(s) of encode_bit()
13 Correct 3546 ms 7344 KB Output is correct - 48208 call(s) of encode_bit()
14 Correct 2028 ms 5652 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1986 ms 5724 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2364 ms 6816 KB Output is correct - 33199 call(s) of encode_bit()
17 Correct 2423 ms 6760 KB Output is correct - 32992 call(s) of encode_bit()
18 Correct 3288 ms 7508 KB Output is correct - 47289 call(s) of encode_bit()
19 Correct 2856 ms 6744 KB Output is correct - 46802 call(s) of encode_bit()
20 Correct 3350 ms 7864 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3887 ms 8352 KB Output is correct - 52427 call(s) of encode_bit()
22 Correct 3735 ms 7816 KB Output is correct - 56170 call(s) of encode_bit()
23 Correct 3935 ms 9088 KB Output is correct - 60188 call(s) of encode_bit()