| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1025975 |
2024-07-17T12:04:45 Z |
AdamGS |
Shopping (JOI21_shopping) |
C++17 |
|
116 ms |
12196 KB |
#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
int n, l, r, ile;
vector<int>pos;
vector<bool>bits;
void check() {
int a=0, b=0;
rep(i, 20) if(bits[i]) a|=1<<i;
rep(i, 20) if(bits[i+20]) b|=1<<i;
vector<int>tmp;
bool zawiera=true;
rep(i, pos.size()) if((i<a || i>b) && (l<=pos[i] && pos[i]<=r)) zawiera=false;
if(zawiera) {
SendA(1);
rep(i, pos.size()) if(pos[a]<=pos[i] && pos[i]<=pos[b]) tmp.pb(pos[i]);
} else {
SendA(0);
rep(i, pos.size()) if(pos[a]>pos[i] || pos[i]>pos[b]) tmp.pb(pos[i]);
}
pos=tmp;
bits.clear();
}
}
void InitA(int _N, int _L, int _R) {
n=_N; l=_L; r=_R;
ile=0;
pos.clear();
bits.clear();
rep(i, n) pos.pb(i);
}
void ReceiveA(bool x) {
bits.pb(x);
if(bits.size()==40 && ile<18) check();
}
int Answer() {
vector<int>T;
rep(i, pos.size()) {
int x=0;
rep(j, 20) if(bits[i*20+j]) x|=1<<j;
T.pb(x);
}
pair<int,int>mi={n, n};
rep(i, pos.size()) if(l<=pos[i] && pos[i]<=r) mi=min(mi, {T[i], pos[i]});
return mi.nd;
}
#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
const int LIM=1e6+7;
int lewo[LIM], prawo[LIM], odw[LIM], n, ile;
pair<int,int>xd;
vector<int>T, pos;
void send() {
int m=pos.size();
vector<pair<int,int>>P, S;
rep(i, m) {
lewo[i]=prawo[i]=i;
odw[i]=0;
P.pb({T[pos[i]], i});
}
sort(all(P));
reverse(all(P));
for(auto i : P) {
int l=i.nd, r=i.nd;
if(l && odw[l-1]) {
lewo[r]=lewo[l-1];
prawo[lewo[r]]=r;
l=lewo[r];
}
if(r<m-1 && odw[r+1]) {
prawo[l]=prawo[r+1];
lewo[prawo[l]]=l;
r=prawo[l];
}
S.pb({l, r});
}
pair<int,int>mi={LIM, LIM};
rep(i, m) {
int d=S[i].nd-S[i].st+1;
mi=min(mi, {max(d, (int)pos.size()-d), i});
}
xd=S[mi.nd];
rep(i, 20) if(S[mi.nd].st&(1<<i)) SendB(1); else SendB(0);
rep(i, 20) if(S[mi.nd].nd&(1<<i)) SendB(1); else SendB(0);
}
}
void InitB(int _N, vector<int>_T) {
n=_N; ile=0;
T=_T;
pos.clear();
rep(i, n) pos.pb(i);
send();
}
void ReceiveB(bool y) {
++ile;
vector<int>tmp;
if(y) {
rep(i, pos.size()) if(xd.st<=i && i<=xd.nd) tmp.pb(pos[i]);
} else {
rep(i, pos.size()) if(xd.st>i || i>xd.nd) tmp.pb(pos[i]);
}
pos=tmp;
if(ile<18) {
send();
return;
}
rep(i, pos.size()) {
rep(j, 20) if(T[pos[i]]&(1<<j)) SendB(1); else SendB(0);
}
}
Compilation message
Anna.cpp: In function 'void {anonymous}::check()':
Anna.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Anna.cpp:19:5: note: in expansion of macro 'rep'
19 | rep(i, pos.size()) if((i<a || i>b) && (l<=pos[i] && pos[i]<=r)) zawiera=false;
| ^~~
Anna.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Anna.cpp:22:7: note: in expansion of macro 'rep'
22 | rep(i, pos.size()) if(pos[a]<=pos[i] && pos[i]<=pos[b]) tmp.pb(pos[i]);
| ^~~
Anna.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Anna.cpp:25:7: note: in expansion of macro 'rep'
25 | rep(i, pos.size()) if(pos[a]>pos[i] || pos[i]>pos[b]) tmp.pb(pos[i]);
| ^~~
Anna.cpp: In function 'int Answer()':
Anna.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Anna.cpp:44:3: note: in expansion of macro 'rep'
44 | rep(i, pos.size()) {
| ^~~
Anna.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Anna.cpp:50:3: note: in expansion of macro 'rep'
50 | rep(i, pos.size()) if(l<=pos[i] && pos[i]<=r) mi=min(mi, {T[i], pos[i]});
| ^~~
Bruno.cpp: In function 'void ReceiveB(bool)':
Bruno.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Bruno.cpp:59:5: note: in expansion of macro 'rep'
59 | rep(i, pos.size()) if(xd.st<=i && i<=xd.nd) tmp.pb(pos[i]);
| ^~~
Bruno.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Bruno.cpp:61:5: note: in expansion of macro 'rep'
61 | rep(i, pos.size()) if(xd.st>i || i>xd.nd) tmp.pb(pos[i]);
| ^~~
Bruno.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
Bruno.cpp:68:3: note: in expansion of macro 'rep'
68 | rep(i, pos.size()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4760 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4760 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2712 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4764 KB |
Output is correct |
| 6 |
Runtime error |
4 ms |
332 KB |
Execution killed with signal 13 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4760 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2716 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4760 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2712 KB |
Output is correct |
| 5 |
Correct |
6 ms |
4764 KB |
Output is correct |
| 6 |
Runtime error |
4 ms |
332 KB |
Execution killed with signal 13 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
116 ms |
12196 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
