Submission #35196
Source Code Expand
#include<cstdio> #include<vector> #include"grader.h" #include"honest.h" #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; void identify(int n){ vector<int> group[100001]; rep(i,n) group[question(2,i,77)].push_back(i); vector< vector<int> > Us,Ls; // 不明グループ, 嘘つきグループ vector<int> U,L; // Us, Ls それぞれの代表 rep(i,n+1) if(!group[i].empty()) { if(group[i].size()==i){ Us.push_back(group[i]); U.push_back(group[i][0]); } else{ Ls.push_back(group[i]); L.push_back(group[i][0]); } } // 確実に嘘つきであるグループがある if(!L.empty()){ int i_honest=-1; rep(i,U.size()) if(question(1,L[0],U[i])==0) i_honest=i; rep(i,U.size()) rep(j,Us[i].size()) answer(Us[i][j],i==i_honest?1:0); rep(i,L.size()) rep(j,Ls[i].size()) answer(Ls[i][j],0); } // 全員正直者かもしれない else{ int i_cand=-1; rep(i,U.size()) if(question(1,U[0],U[i])==0) i_cand=i; if(i_cand==-1){ // 全員正直 or 全員嘘つき if(U.size()>=2){ rep(i,n) answer(i,0); } else{ impossible(); } } else{ // 0 or i_cand が正直者 if(U.size()>=3){ int b=question(1,U[0],U[i_cand==1?2:1]); rep(i,U.size()) rep(j,Us[i].size()) answer(Us[i][j],i==(b==0?0:i_cand)?1:0); } else{ // 特定できない impossible(); } } } }
Submission Info
Submission Time | |
---|---|
Task | C - しょうじききつね と うそつきにんげん (Honest Fox and Dishonest Man) |
User | fura2 |
Language | IOI-Style C++ (GCC 5.4.1) |
Score | 100 |
Code Size | 1400 Byte |
Status | AC |
Exec Time | 219 ms |
Memory | 23896 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 16 / 16 | 29 / 29 | 17 / 17 | 38 / 38 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | subtask0/1, subtask0/10, subtask0/11, subtask0/12, subtask0/13, subtask0/14, subtask0/15, subtask0/16, subtask0/17, subtask0/2, subtask0/3, subtask0/4, subtask0/5, subtask0/6, subtask0/7, subtask0/8, subtask0/9, subtask1/1, subtask1/10, subtask1/11, subtask1/12, subtask1/13, subtask1/14, subtask1/15, subtask1/16, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask1/8, subtask1/9 |
Subtask2 | subtask0/1, subtask0/10, subtask0/11, subtask0/12, subtask0/13, subtask0/14, subtask0/15, subtask0/16, subtask0/17, subtask0/2, subtask0/3, subtask0/4, subtask0/5, subtask0/6, subtask0/7, subtask0/8, subtask0/9, subtask2/1, subtask2/10, subtask2/11, subtask2/12, subtask2/13, subtask2/14, subtask2/15, subtask2/16, subtask2/17, subtask2/18, subtask2/19, subtask2/2, subtask2/20, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask2/7, subtask2/8, subtask2/9 |
Subtask3 | subtask0/1, subtask0/10, subtask0/11, subtask0/12, subtask0/13, subtask0/14, subtask0/15, subtask0/16, subtask0/17, subtask0/2, subtask0/3, subtask0/4, subtask0/5, subtask0/6, subtask0/7, subtask0/8, subtask0/9, subtask34/1, subtask34/10, subtask34/11, subtask34/12, subtask34/13, subtask34/14, subtask34/15, subtask34/16, subtask34/17, subtask34/18, subtask34/19, subtask34/2, subtask34/20, subtask34/21, subtask34/22, subtask34/23, subtask34/24, subtask34/25, subtask34/26, subtask34/27, subtask34/28, subtask34/29, subtask34/3, subtask34/30, subtask34/4, subtask34/5, subtask34/6, subtask34/7, subtask34/8, subtask34/9 |
Subtask4 | subtask0/1, subtask0/10, subtask0/11, subtask0/12, subtask0/13, subtask0/14, subtask0/15, subtask0/16, subtask0/17, subtask0/2, subtask0/3, subtask0/4, subtask0/5, subtask0/6, subtask0/7, subtask0/8, subtask0/9, subtask34/1, subtask34/10, subtask34/11, subtask34/12, subtask34/13, subtask34/14, subtask34/15, subtask34/16, subtask34/17, subtask34/18, subtask34/19, subtask34/2, subtask34/20, subtask34/21, subtask34/22, subtask34/23, subtask34/24, subtask34/25, subtask34/26, subtask34/27, subtask34/28, subtask34/29, subtask34/3, subtask34/30, subtask34/4, subtask34/5, subtask34/6, subtask34/7, subtask34/8, subtask34/9 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0/1 | AC | 69 ms | 17360 KB |
subtask0/10 | AC | 67 ms | 17372 KB |
subtask0/11 | AC | 68 ms | 17428 KB |
subtask0/12 | AC | 67 ms | 17432 KB |
subtask0/13 | AC | 70 ms | 17364 KB |
subtask0/14 | AC | 67 ms | 17372 KB |
subtask0/15 | AC | 68 ms | 17444 KB |
subtask0/16 | AC | 68 ms | 17436 KB |
subtask0/17 | AC | 68 ms | 17360 KB |
subtask0/2 | AC | 68 ms | 17440 KB |
subtask0/3 | AC | 68 ms | 17368 KB |
subtask0/4 | AC | 68 ms | 17440 KB |
subtask0/5 | AC | 67 ms | 17360 KB |
subtask0/6 | AC | 66 ms | 17440 KB |
subtask0/7 | AC | 69 ms | 17360 KB |
subtask0/8 | AC | 68 ms | 17372 KB |
subtask0/9 | AC | 68 ms | 17364 KB |
subtask1/1 | AC | 68 ms | 17368 KB |
subtask1/10 | AC | 67 ms | 17440 KB |
subtask1/11 | AC | 67 ms | 17360 KB |
subtask1/12 | AC | 67 ms | 17372 KB |
subtask1/13 | AC | 71 ms | 17364 KB |
subtask1/14 | AC | 67 ms | 17368 KB |
subtask1/15 | AC | 71 ms | 17372 KB |
subtask1/16 | AC | 67 ms | 17364 KB |
subtask1/2 | AC | 68 ms | 17440 KB |
subtask1/3 | AC | 67 ms | 17368 KB |
subtask1/4 | AC | 68 ms | 17360 KB |
subtask1/5 | AC | 68 ms | 17448 KB |
subtask1/6 | AC | 69 ms | 17444 KB |
subtask1/7 | AC | 68 ms | 17420 KB |
subtask1/8 | AC | 69 ms | 17368 KB |
subtask1/9 | AC | 68 ms | 17376 KB |
subtask2/1 | AC | 70 ms | 17492 KB |
subtask2/10 | AC | 70 ms | 17372 KB |
subtask2/11 | AC | 70 ms | 17488 KB |
subtask2/12 | AC | 69 ms | 17440 KB |
subtask2/13 | AC | 69 ms | 17440 KB |
subtask2/14 | AC | 70 ms | 17356 KB |
subtask2/15 | AC | 69 ms | 17372 KB |
subtask2/16 | AC | 70 ms | 17364 KB |
subtask2/17 | AC | 70 ms | 17432 KB |
subtask2/18 | AC | 70 ms | 17436 KB |
subtask2/19 | AC | 67 ms | 17440 KB |
subtask2/2 | AC | 68 ms | 17568 KB |
subtask2/20 | AC | 68 ms | 17420 KB |
subtask2/3 | AC | 70 ms | 17504 KB |
subtask2/4 | AC | 70 ms | 17364 KB |
subtask2/5 | AC | 71 ms | 17376 KB |
subtask2/6 | AC | 69 ms | 17440 KB |
subtask2/7 | AC | 68 ms | 17504 KB |
subtask2/8 | AC | 72 ms | 17372 KB |
subtask2/9 | AC | 71 ms | 17492 KB |
subtask34/1 | AC | 219 ms | 23832 KB |
subtask34/10 | AC | 179 ms | 19164 KB |
subtask34/11 | AC | 182 ms | 19164 KB |
subtask34/12 | AC | 178 ms | 19232 KB |
subtask34/13 | AC | 177 ms | 19236 KB |
subtask34/14 | AC | 172 ms | 19164 KB |
subtask34/15 | AC | 177 ms | 19156 KB |
subtask34/16 | AC | 180 ms | 19164 KB |
subtask34/17 | AC | 172 ms | 19156 KB |
subtask34/18 | AC | 158 ms | 19244 KB |
subtask34/19 | AC | 176 ms | 19144 KB |
subtask34/2 | AC | 219 ms | 23896 KB |
subtask34/20 | AC | 169 ms | 19000 KB |
subtask34/21 | AC | 182 ms | 19164 KB |
subtask34/22 | AC | 173 ms | 19292 KB |
subtask34/23 | AC | 172 ms | 19028 KB |
subtask34/24 | AC | 158 ms | 19152 KB |
subtask34/25 | AC | 158 ms | 19088 KB |
subtask34/26 | AC | 167 ms | 19092 KB |
subtask34/27 | AC | 168 ms | 19028 KB |
subtask34/28 | AC | 176 ms | 19108 KB |
subtask34/29 | AC | 172 ms | 19084 KB |
subtask34/3 | AC | 216 ms | 23764 KB |
subtask34/30 | AC | 168 ms | 19028 KB |
subtask34/4 | AC | 183 ms | 21196 KB |
subtask34/5 | AC | 170 ms | 19028 KB |
subtask34/6 | AC | 152 ms | 19152 KB |
subtask34/7 | AC | 163 ms | 19156 KB |
subtask34/8 | AC | 173 ms | 19160 KB |
subtask34/9 | AC | 182 ms | 19236 KB |