Submission #1117331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117331		thelegendary08	Message (IOI24_message)	C++17	100 / 100	2715 ms	1180 KiB

message

#include "message.h"
#include<bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define vb vector<bool>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n;i++)
using namespace std;

void send_message(std::vector<bool> m, std::vector<bool> c) {
	vector<vector<int>>v(66, vector<int>(31, -1));
	vb tosend;
	for(int i = 0; i < 1025 - m.size() - 1; i++)tosend.pb(0);
	tosend.pb(1);
	for(int i = 0; i<m.size(); i++)tosend.pb(m[i]);
	vi w;
	f0r(i, 31){
		if(!c[i])w.pb(i);
	}
	w.pb(w[0] + 31);
	vi diffs;
	f0r(i, w.size()-1){
		diffs.pb(w[i+1] - w[i]);
	}
	//for(auto u : diffs)cout<<u<<' ';
	//cout<<'\n';
	f0r(i, diffs.size()){
		f0r(j, diffs[i] - 1){
			v[j][w[i]] = 0;
		}
		//cout<<diffs[i]-1<<' '<<w[i]<<'\n';
		v[diffs[i] - 1][w[i]] = 1;
	}
	
	int ptr = 0;
	f0r(i, 66){
		f0r(j, 31){
			if(v[i][j] == -1){
				if(c[j]){
					v[i][j] = 0;
				}
				else{
					v[i][j] = tosend[ptr];
					ptr++;
					
				}
			}
			
		}
	}
	f0r(i,66){
		f0r(j, 31){
			//cout<<v[i][j]<<' ';
		}
		//cout<<'\n';
	}
	//cout<<'\n';
	f0r(i, 66){
		vb cur;
		f0r(j, 31){
			cur.pb(v[i][j]);
		}
		send_packet(cur);
	}
	/*
  int bts = 20;
  
  vi perm = {863735260, 753594503, 572660336, 85384681, 805750846, 558879905, 26919489, 360184033, 67874300, 84353895, 939819582, 927358721, 925156990, 474491543, 610515434, 512248540, 300602219, 760313750, 403429263, 356426808, 945117276, 816205354, 706953964, 709393584, 491705403, 844760827, 752392754, 400870575, 980258108, 190353236, 337807852}; 
  int n = m.size();
  f0r(i,bts){
    vb v(31);
    f0r(j, 31){
      if(!c[j])v[j] = (perm[j] & (1 << i)) > 0;
      else v[j] = rand() % 2;
    }
    send_packet(v);
  }
  int l = n -1;
  vb tosend;
  f0r(i, 10){
    tosend.pb((1 << i) & l);
  }
  f0r(i, n)tosend.pb(m[i]);
  for(int i = 0; i<tosend.size(); i+=16){
    vb cur;
    int ptr = i;
    f0r(j, 31){
      if(!c[j] && ptr < tosend.size()){
        cur.pb(tosend[ptr]);
        ptr++;
      }
      else cur.pb(0);
    }
    send_packet(cur);
  }
  */
}

std::vector<bool> receive_message(std::vector<std::vector<bool>> r) {
	/*
	f0r(i,66){
		f0r(j, 31)cout<<r[i][j]<<' ';
		cout<<'\n';
	}
	
	*/
	vb ans;
	vi nxt(31);
	vector<vb>dontlook(66, vb(31, 0));
	f0r(i,31){
		int cur = 0;
		while(cur < 66 && r[cur][i] == 0){
			dontlook[cur][i] = 1;
			cur++;
		}
		if(cur != 66)dontlook[cur][i] = 1;
		if(cur != 66)nxt[i] = (i + cur + 1) % 31;
		else nxt[i] = (i + 1) % 31;
	}
	//f0r(i,31)cout<<nxt[i]<<' ';
	//cout<<'\n';
	
	vb ok(31, 0);
	
	
	f0r(i,31){
		vb vis(31, 0);
		int cur = i;
		while(!vis[cur]){
			vis[cur] = 1;
			cur = nxt[cur];
		}
		if(cur == i){
			int cnt = 0;
			f0r(j,31){
				if(vis[j])cnt++;
			}
			if(cnt == 16){
				f0r(j,31){
					if(vis[j])ok[j] = 1;
				}
			}
		}
		
	}
	f0r(i, 66){
		f0r(j,31){
			if(ok[j] && !dontlook[i][j]){
				ans.pb(r[i][j]);
			}
		}
	}
	vb anss;
	bool shutup = 0;
	f0r(i, ans.size()){
		if(!shutup){
			if(ans[i])shutup = 1;
		}
		else{
			anss.pb(ans[i]);
		}
	}
	return anss;
	
	return {};
	/*
  int bts = 20;
  vi perm = {863735260, 753594503, 572660336, 85384681, 805750846, 558879905, 26919489, 360184033, 67874300, 84353895, 939819582, 927358721, 925156990, 474491543, 610515434, 512248540, 300602219, 760313750, 403429263, 356426808, 945117276, 816205354, 706953964, 709393584, 491705403, 844760827, 752392754, 400870575, 980258108, 190353236, 337807852};  int mm = r.size();
  int n = r[0].size();
  vb ans;
  int ptr = 0;
  vb broken(31, 0);
  f0r(i, bts){
    //for(auto u : r[ptr])cout<<u<<' ';
    //cout<<'\n';
    f0r(j, 31){
      if(r[ptr][j] != (((1 << i) & perm[j]) > 0))broken[j] = 1;
    }
    ptr++;
  }
  //for(auto u : broken)cout<<u<<' ';
  //cout<<'\n';
  
  vb valid;
  f0r(i, mm - bts){
    f0r(j,31){
      if(!broken[j])valid.pb(r[ptr][j]);
    }
    ptr++;
  }
  ptr = 0;
  int l = 0;
  f0r(i, 10){
    l += valid[i] * (1 << i);
  }
  l++;
  
  for(int i = 10; i<10 + l; i++){
    ans.pb(valid[i]);
  }
  return ans;
  */
 //return {};
}

Compilation message (stderr)

message.cpp: In function 'void send_message(std::vector<bool>, std::vector<bool>)':
message.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i = 0; i < 1025 - m.size() - 1; i++)tosend.pb(0);
      |                 ~~^~~~~~~~~~~~~~~~~~~~~
message.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i = 0; i<m.size(); i++)tosend.pb(m[i]);
      |                 ~^~~~~~~~~
message.cpp:7:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f0r(i,n) for(int i = 0; i<n;i++)
......
   22 |  f0r(i, w.size()-1){
      |      ~~~~~~~~~~~~~                
message.cpp:22:2: note: in expansion of macro 'f0r'
   22 |  f0r(i, w.size()-1){
      |  ^~~
message.cpp:7:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f0r(i,n) for(int i = 0; i<n;i++)
......
   27 |  f0r(i, diffs.size()){
      |      ~~~~~~~~~~~~~~~              
message.cpp:27:2: note: in expansion of macro 'f0r'
   27 |  f0r(i, diffs.size()){
      |  ^~~
message.cpp: In function 'std::vector<bool> receive_message(std::vector<std::vector<bool> >)':
message.cpp:7:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f0r(i,n) for(int i = 0; i<n;i++)
......
  155 |  f0r(i, ans.size()){
      |      ~~~~~~~~~~~~~                
message.cpp:155:2: note: in expansion of macro 'f0r'
  155 |  f0r(i, ans.size()){
      |  ^~~

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90