oj.uz

답안 #830086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
830086 2023-08-18T18:37:31 Z Antekb 저장 (Saveit) (IOI10_saveit) C++17
0 / 100
 6518 ms 13548 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;
	encode3(V, n, h, m, v1, v2);
	encode2(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

# 결과 실행 시간 메모리 Grader output
1 Correct 6518 ms 13548 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 1573 ms 5956 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 3 ms 4676 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2719 ms 6840 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3235 ms 6868 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3718 ms 7548 KB Output isn't correct
8 Correct 2547 ms 5532 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1546 ms 5564 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1575 ms 5564 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1740 ms 6144 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1802 ms 5416 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3558 ms 7412 KB Output isn't correct
14 Correct 1830 ms 5612 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1930 ms 5808 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2211 ms 7104 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2211 ms 6828 KB Output isn't correct
18 Incorrect 3096 ms 7476 KB Output isn't correct
19 Incorrect 2755 ms 6840 KB Output isn't correct
20 Correct 3292 ms 8036 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3731 ms 8180 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 3711 ms 7664 KB Output isn't correct
23 Correct 4040 ms 8888 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6518 ms 13548 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 1573 ms 5956 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 3 ms 4676 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2719 ms 6840 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3235 ms 6868 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3718 ms 7548 KB Output isn't correct
8 Correct 2547 ms 5532 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1546 ms 5564 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1575 ms 5564 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1740 ms 6144 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1802 ms 5416 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3558 ms 7412 KB Output isn't correct
14 Correct 1830 ms 5612 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1930 ms 5808 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2211 ms 7104 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2211 ms 6828 KB Output isn't correct
18 Incorrect 3096 ms 7476 KB Output isn't correct
19 Incorrect 2755 ms 6840 KB Output isn't correct
20 Correct 3292 ms 8036 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3731 ms 8180 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 3711 ms 7664 KB Output isn't correct
23 Correct 4040 ms 8888 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6518 ms 13548 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 1573 ms 5956 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 3 ms 4676 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2719 ms 6840 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3235 ms 6868 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3718 ms 7548 KB Output isn't correct
8 Correct 2547 ms 5532 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1546 ms 5564 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1575 ms 5564 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1740 ms 6144 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1802 ms 5416 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3558 ms 7412 KB Output isn't correct
14 Correct 1830 ms 5612 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1930 ms 5808 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2211 ms 7104 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2211 ms 6828 KB Output isn't correct
18 Incorrect 3096 ms 7476 KB Output isn't correct
19 Incorrect 2755 ms 6840 KB Output isn't correct
20 Correct 3292 ms 8036 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3731 ms 8180 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 3711 ms 7664 KB Output isn't correct
23 Correct 4040 ms 8888 KB Output is correct - 60188 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6518 ms 13548 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 1573 ms 5956 KB Output is correct - 39510 call(s) of encode_bit()
4 Correct 3 ms 4676 KB Output is correct - 116 call(s) of encode_bit()
5 Correct 2719 ms 6840 KB Output is correct - 66717 call(s) of encode_bit()
6 Correct 3235 ms 6868 KB Output is correct - 69064 call(s) of encode_bit()
7 Incorrect 3718 ms 7548 KB Output isn't correct
8 Correct 2547 ms 5532 KB Output is correct - 21172 call(s) of encode_bit()
9 Correct 1546 ms 5564 KB Output is correct - 21265 call(s) of encode_bit()
10 Correct 1575 ms 5564 KB Output is correct - 21049 call(s) of encode_bit()
11 Correct 1740 ms 6144 KB Output is correct - 35530 call(s) of encode_bit()
12 Correct 1802 ms 5416 KB Output is correct - 15991 call(s) of encode_bit()
13 Incorrect 3558 ms 7412 KB Output isn't correct
14 Correct 1830 ms 5612 KB Output is correct - 24019 call(s) of encode_bit()
15 Correct 1930 ms 5808 KB Output is correct - 25045 call(s) of encode_bit()
16 Correct 2211 ms 7104 KB Output is correct - 33199 call(s) of encode_bit()
17 Incorrect 2211 ms 6828 KB Output isn't correct
18 Incorrect 3096 ms 7476 KB Output isn't correct
19 Incorrect 2755 ms 6840 KB Output isn't correct
20 Correct 3292 ms 8036 KB Output is correct - 50338 call(s) of encode_bit()
21 Correct 3731 ms 8180 KB Output is correct - 52427 call(s) of encode_bit()
22 Incorrect 3711 ms 7664 KB Output isn't correct
23 Correct 4040 ms 8888 KB Output is correct - 60188 call(s) of encode_bit()